Backtracking Explained: Choose, Explore, Un-choose, Prune

Backtracking is how a program searches when there is no formula: build a candidate one choice at a time, and the moment a path cannot lead anywhere, step back and try the next option. Sudoku solvers, N-Queens, "all subsets", "all permutations", word search in a grid and generating balanced brackets are all the same three lines wrapped in different rules. Learn the rhythm once and those problems stop being separate things to memorise.

The problem it solves

Some questions ask for every arrangement that satisfies a rule, or for one arrangement that does: all orderings of a set, every way to make a sum from coins, a placement of eight queens where none attack. The answers live at the leaves of a decision tree. Each level is one decision, each branch one option, and a path from the root to a leaf is one complete candidate.

You could generate every leaf and filter at the end. That is brute force, and its cost is the size of the whole tree. Backtracking walks the same tree depth-first, keeps only the current path in memory, and, crucially, can refuse to enter a branch the moment its partial path already breaks a rule. That refusal is pruning, and it is where all the speed comes from.

The intuition

Every backtracking function has the same skeleton:

1. Base case. If the path is complete, record a copy of it and return.
2. Loop over the options still available at this level.
3. Choose: append the option to the shared path.
4. Explore: recurse to extend the path.
5. Un-choose: pop the option, so the path is exactly as it was before this iteration.

One list, path, serves the entire search. That only works because every append is matched by a pop: when the recursion returns, the path must look untouched so the next option starts from the right place. The copy in the base case matters for the same reason; the path will keep changing after you record it.

Pruning is a check before the recursive call: if this partial path already breaks a rule, skip the branch, and every leaf beneath it disappears without being built. A good prune turns an exponential search into one that is merely large. If you have already met recursion, backtracking is recursion plus a shared, undoable path.

Watch it run

The animation runs the lesson's permute on a, b and c. Backtracking builds an answer one choice at a time: the path starts empty and every option is a branch. Choose a: append it to the shared path and recurse on what is left. Choose b, the same way. Nothing is left to choose, so abc is a complete answer, and a copy of the path is recorded: out.append(path[:]), one solution banked. Now the branch has to be undone. path.pop() removes c; that undo is what lets a single shared list serve the whole search. Pop again, back at a, and the loop moves on to the next option it had not tried. Choose c this time: everything above this node was reused, and only the tail of the path changed. acb is the second answer. Repeat for the b and c branches and there are 6 permutations, one leaf each, with one shared path list throughout. Choose, explore, un-choose; add a rule a partial path can break, and whole subtrees are pruned before they are built.

The code

First the lesson's permute, with a call counter, and the two bugs everybody writes once: storing the path instead of a copy, and forgetting the pop:

import itertools
import math
import random

calls = 0

def permute(left, path, out):
    global calls
    calls += 1
    if not left:                                # complete: record a COPY
        out.append(path[:])
        return
    for i, x in enumerate(left):
        path.append(x)                          # choose
        permute(left[:i] + left[i + 1:], path, out)   # explore
        path.pop()                              # un-choose

out = []
permute(["a", "b", "c"], [], out)
print(len(out), out[:2], calls)        # 6 [['a', 'b', 'c'], ['a', 'c', 'b']] 16

def permute_no_copy(left, path, out):
    if not left:
        out.append(path)                        # BUG: the shared list itself
        return
    for i, x in enumerate(left):
        path.append(x)
        permute_no_copy(left[:i] + left[i + 1:], path, out)
        path.pop()

def permute_no_pop(left, path, out):
    if not left:
        out.append(path[:])
        return
    for i, x in enumerate(left):
        path.append(x)                          # BUG: never un-chosen
        permute_no_pop(left[:i] + left[i + 1:], path, out)

bad1, bad2 = [], []
permute_no_copy(["a", "b", "c"], [], bad1)
permute_no_pop(["a", "b", "c"], [], bad2)
print(bad1)                                     # [[], [], [], [], [], []]
print(bad2[1])                                  # ['a', 'b', 'c', 'c', 'b']

Sixteen calls for six answers: one root, three, six and six nodes on the levels below. Without the copy, all six entries are the same list object, emptied by the final pops. Without the pop, the second "answer" still carries the first one's letters.

Now pruning. Balanced brackets with n pairs: rather than build all 2²ⁿ strings and filter, two rules stop a branch before it can go wrong. And combination sum, where sorting the candidates lets one break cut off every larger candidate at once:

def parens(n):
    """Every balanced string of n pairs; prune before a rule can break."""
    out, path, nodes = [], [], 0
    def go(opened, closed):
        nonlocal nodes
        nodes += 1
        if len(path) == 2 * n:
            out.append("".join(path))
            return
        if opened < n:                          # rule 1: at most n opens
            path.append("("); go(opened + 1, closed); path.pop()
        if closed < opened:                     # rule 2: never close more than opened
            path.append(")"); go(opened, closed + 1); path.pop()
    go(0, 0)
    return out, nodes

def balanced(s):
    depth = 0
    for ch in s:
        depth += 1 if ch == "(" else -1
        if depth < 0:
            return False
    return depth == 0

found, nodes = parens(4)
print(len(found), nodes, 2 ** 9 - 1)            # 14 64 511

def combination_sum(cands, target, prune=True):
    """Multisets of cands (reuse allowed) summing to target."""
    cands, out, path, nodes = sorted(cands), [], [], 0
    def go(start, remaining):
        nonlocal nodes
        nodes += 1
        if remaining == 0:
            out.append(path[:])
            return
        if remaining < 0:
            return                              # only reached without pruning
        for i in range(start, len(cands)):
            if prune and cands[i] > remaining:
                break                           # sorted: every later one is bigger
            path.append(cands[i])
            go(i, remaining - cands[i])         # i, not i + 1: reuse allowed
            path.pop()
    go(0, target)
    return out, nodes

print(combination_sum([2, 3, 6, 7], 7))                          # ([[2, 2, 3], [7]], 10)
print(combination_sum([2, 3, 6, 7], 30)[1], combination_sum([2, 3, 6, 7], 30, False)[1])   # 391 646

Four pairs: the pruned tree has 64 nodes, against 511 in the full tree of all 256 strings. Combination sum visits 391 nodes instead of 646 for the same answers. Finally, everything is checked by brute force: brackets against filtered itertools.product and the Catalan numbers, permutations against itertools.permutations with the call count n!/(n-k)! summed over levels, and combination sum against combinations_with_replacement on 300 seeded inputs, with and without pruning:

ok = True
for n in range(1, 9):
    brute = sorted("".join(p) for p in itertools.product("()", repeat=2 * n) if balanced(p))
    ok &= sorted(parens(n)[0]) == brute and len(brute) == math.comb(2 * n, n) // (n + 1)
for n in range(7):
    calls, got = 0, []
    permute(list(range(n)), [], got)
    ok &= got == [list(p) for p in itertools.permutations(range(n))]
    ok &= calls == sum(math.perm(n, k) for k in range(n + 1))
for seed in range(300):
    r = random.Random(seed)
    cands, target = r.sample(range(1, 12), r.randint(1, 5)), r.randint(1, 25)
    brute = sorted(list(c) for k in range(1, target // min(cands) + 1)
                   for c in itertools.combinations_with_replacement(sorted(cands), k)
                   if sum(c) == target)
    ok &= sorted(combination_sum(cands, target)[0]) == brute
    ok &= sorted(combination_sum(cands, target, prune=False)[0]) == brute
print(ok)                                       # True

The complexity

• Time: proportional to the nodes visited, times the work per node. Permutations: about n · n!, counting the copies. Subsets: 2ⁿ leaves.
• Space: the recursion depth plus one path, O(depth), excluding the output.
• Pruning never changes the worst case on paper, but it changes which nodes exist in practice, often by orders of magnitude.

Where it goes wrong

• Recording the path, not a copy. Every answer becomes the same list.
• A missing or misplaced pop. Later branches inherit stale choices.
• Pruning on the wrong condition. A prune that can reject a branch with valid leaves silently loses answers; cross-check against brute force on small inputs.
• Duplicates in the input. Sort, then skip an option equal to the previous one at the same level, as in the subsets and permutations article.
• Overlapping subproblems. If you only need a count or an optimum, dynamic programming may replace the search.

When it shows up in interviews

Whenever the question says "all", "every", "generate" or "find any arrangement": permutations, subsets, combination sum, brackets, N-Queens, Sudoku and word search. Interviewers watch for the copy, the pop, a clear prune and an honest complexity estimate. The patterns cheat sheet lists the signals next to the other techniques.

How to say it in an interview

"This is a search over a decision tree, so I'll backtrack. I keep one shared path: at each level I loop over the valid options, append one, recurse, then pop it so the path is restored for the next option. When the path is complete I record a copy. To keep it fast I prune before recursing: here, I never close more brackets than I opened. The cost is the number of nodes visited, exponential in the worst case, and the extra space is the recursion depth."