What Is Backtracking? The Recursion Pattern Behind Every Decision Tree

You are writing a Sudoku solver. At each empty cell, you try a digit, move to the next cell, try another digit, and keep going. When you reach a contradiction, you erase the last digit you wrote and try the next one. That erasing step is backtracking. Not a special algorithm. Just recursion with one deliberate addition: undo what you did before you return.

A backtracking algorithm systematically explores a decision tree by making choices, recursing into them, and unmaking those choices on the way out. The undo step is what separates it from plain DFS, and it is the part most beginners forget, usually at the worst possible moment.

Three Steps, Every Time

Every backtracking solution has the same skeleton:

Choose, pick one option from the available candidates
Explore, recurse with that choice in place
Undo, remove the choice so the next sibling branch starts clean

The structure never changes. What changes is what "choose" and "undo" mean for your specific problem.

def backtrack(state, start):
    if is_complete(state):
        results.append(state[:])  # copy, not reference
        return

    for candidate in candidates_from(start):
        state.append(candidate)      # choose
        backtrack(state, next_start) # explore
        state.pop()                  # undo

The state[:] on the base case matters more than it looks. If you append state directly, every entry in results points to the same list object. By the time recursion finishes, they will all be empty. You will stare at a list of empty lists for a good thirty seconds before realizing what you did.

Subsets: Tracing the Tree

The cleanest entry point is generating all subsets of [1, 2, 3]. At each index, you decide whether to include that element, then recurse on the rest.

def subsets(nums: list[int]) -> list[list[int]]:
    results = []

    def backtrack(index: int, current: list[int]) -> None:
        results.append(current[:])  # every state is a valid subset

        for i in range(index, len(nums)):
            current.append(nums[i])     # choose
            backtrack(i + 1, current)   # explore
            current.pop()              # undo

    backtrack(0, [])
    return results

Trace through [1, 2, 3]: the first call records [], then appends 1 and recurses. That subtree records [1], [1,2], [1,2,3], and [1,3] before popping back. The second top-level iteration takes 2, producing [2], [2,3], then [3] last. You end up with all 8 subsets, every one captured at the moment it was valid.

The Undo Step Is the Whole Algorithm

The undo step is what makes a single shared list safe to use across every branch of the recursion tree. Without current.pop(), every recursive call appends to the same accumulating list. When you finish exploring [1, 2, 3] and try to explore [1, 3], you are appending onto [1, 2, 3] instead of [1]. Your output looks like someone sneezed on a whiteboard.

An alternative is passing a fresh copy into every recursive call: backtrack(i + 1, current + [nums[i]]). This avoids the undo step but creates a new list at every call, costing O(n) extra memory per frame. The undo pattern keeps space at O(depth) because you maintain exactly one list throughout.

The same pattern shows up in every backtracking problem, just wearing different clothes:

# Permutations: mark/unmark instead of append/pop
def permute(nums: list[int]) -> list[list[int]]:
    results = []
    used = [False] * len(nums)

    def backtrack(current: list[int]) -> None:
        if len(current) == len(nums):
            results.append(current[:])
            return
        for i, num in enumerate(nums):
            if used[i]:
                continue
            used[i] = True         # choose
            current.append(num)
            backtrack(current)     # explore
            current.pop()          # undo
            used[i] = False

    backtrack([])
    return results

In N-Queens, you place a queen on a row, recurse through the remaining rows, then remove it. In word search, you mark a cell visited, recurse to neighbors, then unmark it. The form changes. The three steps do not.

Ctrl+Z Ctrl+Z Ctrl+Z, the backtracking algorithm, expressed as muscle memory

When you finally understand that state.pop() is just hitting Ctrl+Z before the next branch.

What Is Backtracking vs Plain DFS?

Both use recursion. Both explore a tree structure. The difference is in what that tree is and whether you modify it.

DFS traverses a graph or tree that already exists in memory. You visit nodes, you do not mutate them. A visited set prevents cycles, but you never undo a visit because the node is still there when you leave.

Backtracking builds its tree implicitly by constructing and deconstructing state as it goes. The nodes do not exist until you choose your way into them, and they stop existing when you undo your way back out. That is why the undo step is necessary: you are sharing one mutable state object across all branches, and each branch needs to start from the same clean base.

For a deeper look at exactly where the two patterns diverge in code, see DFS vs Backtracking.

Time and Space: What You Are Signing Up For

Backtracking algorithms are almost always exponential. That is not a flaw. Problems requiring exhaustive exploration have exponential output, so exponential time is unavoidable at worst case.

Problem type	Time complexity	Extra space (stack only)
Subsets of n elements	O(n · 2^n)	O(n)
Permutations of n elements	O(n · n!)	O(n)
k-combinations from n	O(k · C(n, k))	O(k)

The leading factor (n or k) comes from copying state at each leaf. The extra space is O(depth) because you only ever hold one path from root to current node, not the whole tree at once.

The interview question is never "can you beat exponential?" but "can you prune early enough to matter?" Pruning means detecting a dead-end before you reach a leaf and skipping that entire subtree. If a problem asks for subsets summing to a target and your running sum already exceeds it, stop there. That check costs O(1) but can eliminate half the tree.

For the full complexity derivations, including why subsets land at O(n · 2^n) via the binomial theorem, see Backtracking Time Complexity.

"Return All..." Almost Always Means Backtracking

The word "all" is the primary signal. Not "find an element" or "find the maximum." Those lean toward binary search, greedy, or dynamic programming. When a problem says "return all combinations," "generate all permutations," "find all valid arrangements," or "list every possible path," it is almost certainly backtracking.

Secondary clues:

"No element may be used more than once" (implies tracking which elements are in the current state)
A grid with movement and state modification (word search, Sudoku, N-Queens)
A recursive tree where you need every leaf, not just the best one

Once you recognize the signal, the code structure follows directly from the three steps. You rarely need to invent anything new. The hard part is not knowing what to write. It is not forgetting to write the third line.

If you want to practice reading the signal from problem statements before you see any code, How to Spot a Backtracking Problem walks through the prompt-level clues across a range of problem types.

The Two Bugs That End Interviews

Almost every backtracking bug in interviews comes from one of two places.

Forgetting state[:] at the base case. You append state and get a list of references, all pointing to the same object. By the time recursion finishes, every entry is empty or identical. The fix: always copy. Every single time. Even when you are "pretty sure" you do not need to.

Mutating state in the loop body without undoing it. You modify a visited array, a running sum, or a board cell and forget to restore it after the recursive call returns. The fix: write the undo line immediately after you write the explore line, before you forget what you modified. Do not write three more lines of logic and then try to remember what state you touched.

A useful habit: before writing any backtracking solution, type the three-step comments first.

# choose
# explore
# undo

Then fill them in. The scaffold forces you to think about what "undo" means for this specific problem before you are halfway through and confused.

Coding in an interview, everything looks fine until it very much does not

"I ran all my test cases." The test cases: [1]. The actual input: [1, 2, 3, 2, 1].

Practice Before It Costs You

If you want to drill the pattern under timed conditions with feedback on both correctness and communication, SpaceComplexity runs voice-based mock interviews with rubric scoring across backtracking and other DSA categories. Blanking on state.pop() in a practice session costs you nothing. Blanking in the real interview costs you the offer.