Backtracking

1The mental model (what this really is)#

Backtracking is organized trial and error. Build a solution one choice at a time, and the instant a partial choice cannot lead to a valid answer, undo it and try the next option.

The maze picture, because it sticks:

• Pick a direction, walk until you hit a wall, return to the last junction, try the next passage.
• You never teleport to a fresh start. You rewind exactly one decision and continue.
• That rewind-one-step move is the backtrack.

The tree picture, which is the one that earns points:

• Picture a giant tree of all possible decision sequences. The root is the empty solution.
• Each level adds one more choice. The leaves are complete solutions, most of them garbage.
• Brute force walks every leaf, no matter how doomed.
• Backtracking walks the same tree but prunes entire branches the instant they turn invalid, so you never explore the subtree below a bad decision.
• For branching factor b and depth d, one valid prune high in the tree can cut b^(d-1) wasted leaves in a single stroke.

The engine is plain recursion with one twist:

• After you make a choice and recurse, you must undo that choice before trying the next one.
• Make, recurse, unmake.
• Forget the unmake and your state leaks across branches, breaking in confusing ways that are miserable to debug on a whiteboard under time pressure.

2How to recognize it (the signals in a problem)#

Feel the backtracking reflex when a problem asks for any of these.

The loud signals:

• "Find ALL the ..." combinations, permutations, subsets, arrangements, partitions.
• "Generate every valid ..." (every valid parenthesis string, every path, every board placement).
• "How many ways ..." when you actually need to construct the ways, not just count with a formula.
• Constraint puzzles: Sudoku, N-Queens, word search on a grid, graph coloring.
• The answer is a sequence of choices, each drawn from a small set of options.

The sharper tell:

• The problem has a branching decision at each step, and later choices depend on earlier ones.
• If choice 3 is only legal because of what you did at choices 1 and 2, that dependency is the signal.
• A plain for-loop cannot express it, because the legal options change as you go.

The DP-versus-backtracking fork (interviewers grade this in the first 30 seconds):

• Single count or yes/no plus clean overlapping subproblems? Reach for dynamic programming.
• Must enumerate the actual solutions, or constraints so tangled that pruning the search is the realistic move? Backtracking.
• Counting the ways to climb stairs is DP: you return one integer.
• Listing every valid Sudoku completion is backtracking: you return the boards themselves.

3The template (how it works, with pseudocode)#

Almost every backtracking solution fits this shape. Burn it into memory.

function backtrack(state, choices):
    if state is a complete solution:
        record(state)      # or return True for a decision problem
        return

    for option in choices available from state:
        if not valid(option, state):
            continue       # prune: skip illegal options

        make(option, state)             # choose
        backtrack(state, next_choices)  # explore
        unmake(option, state)           # un-choose (the backtrack)

Four moving parts. Naming them out loud keeps you honest:

1. The base case. When is the current partial answer complete? Record it, or signal success.
2. The choice set. What options can I try from here? Often an index into an array, a set of candidates, or the neighbors of a cell.
3. The validity check (pruning). Which options are illegal right now? The earlier you prune, the faster you run, and the difference is exponential, not a constant factor.
4. The make/unmake pair. Mutate shared state going down, restore it coming back up. Every make needs an exactly mirrored unmake.

A tiny concrete skeleton for subsets, so the abstract template feels real:

def subsets(nums):
    res, path = [], []
    def bt(start):
        res.append(path[:])            # every node is a valid subset; copy it
        for i in range(start, len(nums)):
            path.append(nums[i])       # choose
            bt(i + 1)                  # explore the rest
            path.pop()                 # un-choose
    bt(0)
    return res

Notice path[:], because this is the silent killer:

• You append a copy, not the live list.
• Forget it and every stored result points at the same list object, which ends up empty by the time you return (every pop undoes every append).
• That one-character bug has cost people offers. It looks correct and fails silently.

4A worked example (walk through one problem step by step)#

Generate Parentheses. Given n pairs, produce every well-formed combination. For n=2 the answer is (()) and ()().

Frame it as a sequence of choices first:

• The result has 2n characters. At each position I place either ( or ).
• The decision tree has depth 2n and branching factor 2.
• Brute force would be 2^(2n) strings. For n=2 that is 16 candidates, most malformed like ))((.
• We only want the 2 valid ones.

Now the pruning, which is where this problem gets elegant. Track two counters: open brackets used, close brackets used.

• Place ( only if open < n. Once all n open brackets are used, no more.
• Place ) only if close < open. A closing bracket needs an unmatched open to pair with. This single rule kills every invalid string before it forms.

The base case: when the string length hits 2n it is complete and, because of the pruning, guaranteed valid. Record it.

Here is the code, then the trace.

def generate(n):
    res = []
    def bt(cur, open_, close):
        if len(cur) == 2 * n:
            res.append(cur)
            return
        if open_ < n:
            bt(cur + "(", open_ + 1, close)   # place '('
        if close < open_:
            bt(cur + ")", open_, close + 1)   # place ')'
    bt("", 0, 0)
    return res

Trace for n=2, starting at ("", 0, 0):

• open(0) < 2, place (: now ("(", 1, 0). The ( branch runs first, so follow it down before touching ).
• open(1) < 2, place another (: now ("((", 2, 0). Open is maxed, ( branch pruned.
• close(0) < open(2), place ): ("(()", 2, 1). Open still maxed, prune (.
• close(1) < open(2), place ): ("(())", 2, 2). Length 4 = 2n. Record (()).
• Return up the stack to ("(", 1, 0). The ( branch is done, so try ): close(0) < open(1), place ): ("()", 1, 1).
• open(1) < 2, place (: ("()(", 2, 1). Open maxed, prune.
• close(1) < open(2), place ): ("()()", 2, 2). Length 4. Record ()().

What just happened:

• Two results, exactly the valid ones.
• We never built a single malformed string, and never even visited 14 of the 16 brute-force candidates, because the validity checks pruned bad branches at the moment of choice.

One clean trick worth saying out loud:

• I passed cur + "(" as a new string instead of mutating and undoing. That IS backtracking. The unmake happens implicitly because each recursive call got its own copy of the string.
• When state is cheap and immutable, passing a fresh copy is the same pattern with less bookkeeping.
• When state is expensive (a big grid, a visited set), mutate and undo instead, because copying a 9x9 Sudoku board at every node would be slow and wasteful.

5Variations and gotchas#

Same skeleton, different flavors. Know these cold, because interviewers rotate through them and the setup for each takes ten seconds once you spot which one you are in.

The flavors:

• Subsets: at each index, include it or skip it. 2^n leaves.
• Permutations: order matters, so track which elements are already used. n! blowup.
• Combinations: order does not matter, so enforce a start index that only moves forward. This is how you avoid [1,2] and [2,1] as separate answers.
• Partitioning: split a string or array into valid pieces (palindrome partitioning, for example). The choice is where the next piece ends.
• Grid search: word search, islands by DFS, maze paths. Choices are the four neighbors, state is a visited marker you set and clear.

The three gotchas that actually bite:

• Duplicates. When the input has repeats and you want unique results, sort first, then skip an option if it equals the previous one AND the previous one was not used at this position: if i > start and nums[i] == nums[i-1]: continue. Getting this line right under pressure is a real differentiator; most candidates forget the sort or botch the condition and silently emit dupes.
• Copy on record. For any problem that collects lists, append a copy (path[:] or list(path)). For strings you usually get this free, because strings are immutable, so cur + "(" already made a fresh object.
• Mirror the unmake. When state is a mutable grid or set, set a cell, recurse, then reset the exact same cell to its exact old value. One asymmetry and you get phantom results that are nearly impossible to spot by reading the code.

6Complexity#

Be honest with yourself: backtracking is usually exponential, and that is fine, because the problem itself demands enumerating exponentially many things.

What pruning does and does not do:

• It does not change the big-O class.
• It changes the constant, and more importantly cuts branches that produce nothing.

Rough bounds you can quote:

• Subsets: O(n times 2^n) time. There are 2^n subsets and copying each costs up to n.
• Permutations: O(n times n!) time.
• Combinations of k from n: O(k times C(n, k)).
• Generate Parentheses: bounded by the nth Catalan number, roughly 4^n / n^1.5.

Space:

• Typically O(depth) for the recursion stack plus O(n) for the current path, not counting the output you must return.
• For a tree of depth d you hold at most d frames at once.
• If the question asks for all answers, the output size itself is exponential and there is no way around that.

The output can be exponential, so we cannot beat that. The job is to avoid wasting work on branches that cannot produce valid output.

That line is the honest framing in an interview. It shows you understand the floor and are not pretending to a magic polynomial trick that does not exist.

7Mistakes that cost people the round#

The failure list, in rough order of how often it kills a round:

• Forgetting the unmake. You mutate shared state, recurse, and never restore it. State bleeds across branches. This is the number one backtracking bug in live interviews, and the first thing a sharp interviewer looks for.
• Storing references instead of copies. You push the live path into results, keep mutating it, and every stored answer ends up identical (usually empty). Always copy at the base case.
• Pruning too late or not at all. Check validity only at the leaves and you have written brute force with extra steps. Check at the moment of choice so you cut whole subtrees, not single leaves.
• Wrong base case. Off by one on length, or recording at the wrong depth, and you emit partial or duplicate answers.
• Botching duplicate handling. No sort first, or the skip condition written wrong, so you either miss answers or produce dupes.
• Freezing because it looks hard. Say out loud: "This is a choose-explore-unchoose over a decision tree." Write the four-part template, then fill the blanks. Interviewers reward the structured derivation even more than a perfect first pass, because it shows how you attack a problem you have never seen.

8Your practice path (named problems by difficulty)#

Do these in order. Each one adds exactly one new idea, so you build the pattern instead of memorizing solutions. Short on time? The five-problem core is Subsets, Permutations, Combination Sum, Word Search, and N-Queens; they cover every mechanic in the pattern.

Start here (warm up the reflex):

• Subsets
• Combinations
• Permutations
• Letter Combinations of a Phone Number
• Generate Parentheses

Build the core (pruning and duplicates):

• Subsets II
• Permutations II
• Combination Sum
• Combination Sum II
• Palindrome Partitioning
• Word Search

Prove you own it (heavy pruning, grid constraints):

• N-Queens
• Sudoku Solver
• Restore IP Addresses
• Word Break II
• Partition to K Equal Sum Subsets

Why those last two are the ceiling:

• Do N-Queens and Sudoku Solver cleanly, explaining your pruning as you go, and you are ready for anything in this family.
• The pruning carries the whole solution. A naive search times out.

Check the company guides to see exactly which rounds and companies tend to reach for this pattern.