Backtracking

What backtracking is

Backtracking is DFS over a decision tree: at each step, try a choice, recurse deeper with that choice applied, then undo it and try the next. The undo is the defining move - one shared, mutable partial solution is threaded through the whole search instead of copying state at every node, and 'unchoose' restores it exactly as it was.

It is the honest tool for problems whose output is exponential (all subsets, all permutations) or whose structure resists anything smarter (N-Queens, Sudoku). You cannot beat exponential output size - the craft is in not exploring branches that cannot succeed.

How to recognize it

Signals: 'all', 'generate every', 'enumerate' - all subsets, all permutations, all valid combinations, all palindromic partitions. Also constraint-satisfaction puzzles asking for any valid arrangement under interacting rules.

The counterpart signal: if the ask is 'count the ways' or 'find the best one' without listing them, dynamic programming often replaces the enumeration at polynomial cost. 'List them' is backtracking; 'count them' deserves a DP attempt first.

The choose-explore-unchoose template

Every backtracking solution is the same skeleton: a recursive function carrying the partial solution and a position marker; a base case that records a completed candidate (copy it! it is shared state); a loop over available choices, each wrapped in choose -> recurse -> unchoose. Design questions per problem: what is a choice, what makes the candidate complete, and what lets you rule a branch out early.

def backtrack(start, path):
    if complete(path):
        results.append(copy(path))     # copy - path is shared
        return
    for choice in options(start):
        if not viable(choice): continue   # prune
        path.append(choice)               # choose
        backtrack(next_position, path)    # explore
        path.pop()                        # unchoose

Pruning and duplicates

Pruning is what makes exponential search usable: check constraints at choice time, not at leaf time. In N-Queens, testing column and diagonal conflicts before placing prunes almost the entire tree; validating full boards at the leaves is astronomically slower.

Duplicate outputs come from equal elements being chosen in different orders. The standard cure: sort the input, then at each depth skip an element equal to its unused predecessor ('if i > start and a[i] == a[i-1]: continue'). That yields each distinct candidate exactly once without a dedupe set.

Common pitfalls

Appending the shared path itself instead of a copy at the base case - every recorded result later mutates into the same empty list.

Forgetting the unchoose step, or unchoosing a different amount than was chosen - the state corrupts silently and later branches see ghosts.

Wrong duplicate-skip condition: 'i > start' (skip within the same depth) not 'i > 0' (which also bans legitimate reuse across depths).

Pruning too late: any check performable before the recursive call must happen there.

Passing index-1 style mistakes: subsets/combinations advance the start index (order does not matter); permutations track a used set instead (order matters). Mixing the two produces duplicates or omissions.

Worked examples

def backtrack(start, path):
    results.append(copy(path))     # every node is a subset
    for i in start .. n-1:
        path.append(a[i])
        backtrack(i + 1, path)
        path.pop()
backtrack(0, [])

def backtrack(path):
    if len(path) == n:
        results.append(copy(path)); return
    for i in 0 .. n-1:
        if used[i]: continue
        used[i] = true; path.append(a[i])
        backtrack(path)
        path.pop(); used[i] = false
backtrack([])

def place(row):
    if row == n: record(board); return
    for col in 0 .. n-1:
        if col in cols or (row-col) in diag1 or (row+col) in diag2: continue
        add col, row-col, row+col to the sets; board[row] = col
        place(row + 1)
        remove them                      # unchoose all three
place(0)

Check yourself

Try to answer before revealing - retrieving from memory is what makes it stick.

Frequently asked questions