Backtracking

Backtracking is depth-first search over a tree of decisions. At each node you make a choice, recurse into the consequences of that choice, and when you return from the recursion you undo the choice before trying the next option at that same level. The state you are building — a partial permutation, a partial subset, a partial board — is mutated in place as you descend, and un-mutated as you climb back up. That "undo" step is the entire idea: rather than copying the state at every branch, you share one mutable structure across the whole search and carefully restore it, which is what makes backtracking memory-efficient compared to naively branching a tree of full copies.

Every backtracking solution is built from three ingredients. First, the choice: what are the options available at this step (which number to place next, whether to include or exclude an element, which letter to pick for the current digit)? Second, the constraint: a check that lets you abandon a branch the moment it can no longer lead to a valid answer — a queen already under attack, a running sum that has exceeded the target, a digit with no letters left. This check is called pruning, and it is what separates backtracking from plain brute force: instead of generating every combination and filtering afterward, you cut off invalid branches as early as possible, often before doing most of the wasted work. Third, the goal: the condition under which a partial solution is actually complete and should be recorded, such as the partial permutation reaching the input's length, or the running sum hitting the target exactly.

The generic template looks like this:

def backtrack(partial, choices_remaining):
    if is_goal(partial):
        record(copy of partial)
        return
    for choice in candidates(choices_remaining):
        if not violates_constraint(partial, choice):
            partial.append(choice)              # choose
            backtrack(partial, remaining_after(choices_remaining, choice))  # explore
            partial.pop()                        # un-choose

The choose -> explore -> un-choose rhythm is the heartbeat of every problem in this subject. It is worth internalizing as muscle memory, because the problems mostly differ only in what counts as a "choice" and what counts as a "constraint."

Backtracking is exponential in the worst case — for permutations of n items there are n! leaves, for subsets there are 2^n, and for N-Queens the naive search space is n^n before pruning. What makes it usable in practice is that good constraint checks eliminate huge swaths of the tree without ever visiting them: N-Queens with column and diagonal tracking prunes to roughly O(n!) instead of O(n^n), and combination-sum with sorted candidates can stop scanning a level the instant the running sum would exceed the target. Space is typically O(depth) for the recursion stack, plus O(depth) for the partial solution currently being built, plus whatever space is needed to store all the recorded answers.

Three pitfalls trip people up repeatedly. First, forgetting to undo a choice (the pop(), or resetting a used/visited flag) before trying the next option at the same level — this silently corrupts every subsequent branch of the search. Second, appending a reference to the mutable partial-solution list when recording an answer instead of a copy (result.append(list(partial)) or partial[:]) — since the list keeps changing after you record it, every recorded "answer" ends up pointing at the same final, usually empty, list. Third, when the input contains duplicate values, forgetting to explicitly skip duplicate choices at each level, which produces duplicate answers in the output.

This subject applies the pattern to five problems, each of which isolates one of these ideas:

1. Find All Permutations — the pure "choose one of the remaining items" pattern with a used-set.
2. Find All Subsets — the "include or exclude" pattern, decided per index.
3. N-Queens — choices with several simultaneous constraints (column, and both diagonals).
4. Combinations of a Sum — choices with unlimited reuse, pruned by a running sum and a sorted candidate list.
5. Phone Keypad Combinations — choices driven by a lookup table, one digit at a time, with no numeric constraint at all — just a length-based goal.