Backtracking

Use backtracking when the answer is built through choices and no safe rule lets you commit to only one branch. Typical tasks enumerate combinations, assign positions, or search paths under constraints. The first design decision is what one level chooses.

1. Model a Decision Tree with No Missing or Repeated Answers

State what has been chosen, what remains available, and when a result is complete.

For N queens, choosing one column per row avoids even generating boards with two queens in a row. This reduces the search far more than optimizing how a board is copied. Prefer a model that rules out invalid structure before relying on later pruning.

The same tree supports several return types: stop early for feasibility, collect snapshots for enumeration, add child counts for counting, and take the best child value for optimization. An empty partial choice can itself be a valid answer, as with the empty subset; valid answers need not occur only at leaves.

2. Recipe: Choose, Recurse, Undo

The reference chapter uses one backtracking recipe across these tasks. For a concrete example, enumerate unique subsets of an array that may contain duplicates:

def unique_subsets(nums):
    values = sorted(nums)
    result, path = [], []

    def search(start):
        result.append(path.copy())
        for i in range(start, len(values)):
            if i > start and values[i] == values[i - 1]:
                continue
            path.append(values[i])
            search(i + 1)
            path.pop()

    search(0)
    return result

State: path contains values selected at strictly increasing indices; start is the first index still eligible. The recursive call may extend the path, but must restore it before the next sibling branch. Copy when saving an answer, or every result will reference the same mutable list.

Duplicates: skip equal values only among choices at the same depth (i > start). For [1,1], the root skips its second 1, but the child may still choose the other 1, producing [], [1], [1,1]. A global “seen value” set would incorrectly remove [1,1].

For Combination Sum II, add remaining, save only when it reaches zero, and use the same i+1 rule because each input occurrence is used once. If reuse is allowed, as in Combination Sum, recurse with i instead. Positive candidates ensure that repeated use still makes progress.

For permutations, track used indices rather than values. With sorted duplicates, skip an equal candidate when its previous equal occurrence is not used on the current path; this gives equal items a consistent selection order without forbidding repeated values entirely.

3. Prune Only What Cannot Become an Answer

• Constraint failure: a repeated cell invalidates a simple path; a queen attacking an earlier queen invalidates that branch immediately.
• Insufficient remaining choices: if a size-k combination still needs three items and only two remain, stop.
• Monotonic sum: with sorted positive candidates, candidate > remaining lets you stop the loop. With negative numbers, an oversized partial sum may decrease later, so that pruning is invalid.
• Optimization bound: stop only when an optimistic bound on this branch cannot beat the best complete answer found so far. A merely poor current score is not enough.

For Unique Paths III, arriving at the destination is valid only if every required cell has been visited. Mark a cell on entry and restore it on return. A global visited set shared permanently across branches would suppress different valid paths.

4. Count Search Work and Output Separately

For n distinct values, subsets have $2^n$ answers and copying them costs $O(n2^n)$ total. Permutations have $n!$ answers of length n, so materializing them costs $O(n\cdot n!)$. The current path, used-state and recursive stack usually need $O(n)$ space; the returned results are additional, potentially much larger storage.

For less regular trees, sum the visited states and work per state. Branching at most b >= 2 with depth at most d and local work at most A gives the loose bound $O(b^d A)$. Pruning can greatly help real inputs without changing the worst-case class. A single-child chain instead has $O(dA)$ work.

Memoize only when the future answer depends completely on the state key. Counting paths in a right/down grid can reuse (row,col); paths that may move in four directions without revisiting also depend on the visited cells. Caching by cell alone is wrong. Enumeration cannot simply skip a repeated state if different prefixes produce different required outputs.

5. Key Takeaways

• Combinations advance a start index; permutations choose unused indices. Decide whether order matters before coding.
• Every branch must restore shared state, and every saved mutable answer needs a copy.
• Skip duplicates among sibling choices, not everywhere in the search.
• “Remaining sum is negative” is a valid prune only when future choices cannot reduce the sum.

Review Recursion for call contracts and stack costs. Continue to Dynamic Programming when equivalent remaining tasks recur, or Greedy Algorithms when a proof can eliminate all but one choice.