Backtracking

How it works

Backtracking is a depth-first walk over a tree of decisions. Each level of recursion makes one choice, explores everything that follows from it, then undoes the choice and tries the next. The path from the root to the current call is the partial solution.

The template is always choose, explore, unchoose. Because the same path list is reused and mutated, you must copy it when you record an answer and restore it exactly after each recursive call.

What makes backtracking fast enough is pruning. If a partial solution already violates a constraint (the sum is over target, a queen is attacked, a prefix is not a word), return immediately. Good pruning cuts away most of the tree without changing the exponential worst case.

Spot it when the problem says 'all', 'every combination', 'every arrangement' or 'any valid placement', and the input is small (n up to about 15 or 20). Subsets, permutations, combination sums, N-Queens, Sudoku and word search are all the same skeleton.

How to attack it

1. 1Describe one decision per recursion level (include or skip, which item next, which cell).
2. 2Write the base case that records a complete answer (copy the path).
3. 3List the choices at the current level and the pruning test for each.
4. 4Undo every change after the recursive call returns.
5. 5Handle duplicates by sorting and skipping equal neighbors at the same depth.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def combinations_summing_to(candidates, target):
    candidates.sort()      # sorting enables pruning and duplicate skipping
    results, path = [], []

    def backtrack(start, remaining):
        if remaining == 0:
            results.append(path[:])          # record a COPY
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue                     # skip duplicates at this depth
            if candidates[i] > remaining:
                break                        # prune: sorted, so the rest are bigger
            path.append(candidates[i])       # choose
            backtrack(i + 1, remaining - candidates[i])  # explore
            path.pop()                       # unchoose

    backtrack(0, target)
    return results

What it costs