Choose, Explore, Undo

Systematic trial and error

Backtracking builds a candidate solution one choice at a time. When the partial candidate breaks a rule, abandon it and undo the last choice. When it is complete, record it and undo anyway to try the next option. It is depth-first search over a decision tree — a tree where each node is a partial solution and each branch is one possible next choice.

Every backtracking solution is the same loop wearing different clothes:

def backtrack(path, choices):
    if is_complete(path):
        results.append(path[:])   # record a COPY
        return
    for c in choices:
        if not valid(c, path):
            continue              # prune: skip dead branches early
        path.append(c)            # 1. choose
        backtrack(path, next_choices)  # 2. explore
        path.pop()                # 3. undo

The undo step is what makes this different from plain DFS. There is one shared path object, and every branch of the tree borrows it, mutates it, and must hand it back exactly as found. Choose, explore, undo — always in that order.

Worked example: all subsets of [1, 2, 3]

A subset keeps some elements and drops others, preserving order. The cleanest template loops over a start index so each call only considers elements at or after start — which is exactly what prevents generating both [1, 2] and [2, 1]:

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])       # every node in the tree is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])  # choose nums[i]
            backtrack(i + 1, path)
            path.pop()            # undo
    backtrack(0, [])
    return res

Trace it. The root records []. Choose 1: record [1]. Choose 2: record [1, 2]. Choose 3: record [1, 2, 3], no choices left, pop back to [1, 2], pop to [1], choose 3: record [1, 3]. Pop twice, choose 2 at the top level: [2], then [2, 3]. Finally [3]. Eight subsets, which is 2^3 — every element independently in or out.

The big three shapes

Two details here are heavily tested:

• Combination Sum allows reusing a number: after choosing nums[i], recurse with start i so the same element stays available. Passing i + 1 means each element is used at most once; passing 0 breaks the start-index guarantee and produces the same combination in several orders.
• Permutations care about order, so the start-index trick does not apply. Every not-yet-used element is a legal branch, tracked with a used boolean array or by swapping chosen elements to the front.

Duplicates in the input: sort and skip

If the input is [1, 2, 2], the plain subsets template emits [1, 2] twice — once with each 2. The fix has two parts. First sort, so equal values sit next to each other. Then skip a value when it equals its left neighbor at the same tree level:

for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i - 1]:
        continue   # same value, same level: identical subtree
    ...

Why this exact condition: when i > start and nums[i] == nums[i - 1], the loop already explored an identical branch this level using the first copy — the second copy would grow an identical subtree. But when i == start, this is the first time the value appears at this level, and skipping it would wrongly forbid using both 2s together in [1, 2, 2]. The condition is i > start, not i > 0 — memorize the difference.

Prune early, not at the leaves

Checking validity only at complete candidates wastes exponential work on branches that were doomed near the root. Push the checks as early as possible:

• Combination Sum: if the remaining target goes negative, return immediately; with a sorted input you can break the whole loop, since every later candidate is even bigger.
• Palindrome Partitioning: only recurse on a prefix that is already a palindrome — a non-palindrome prefix can never be repaired by later cuts.
• N-Queens: instead of re-scanning the board per placement, keep three sets — occupied columns, diagonals (indexed by row - col), and anti-diagonals (row + col). Validity becomes three O(1) membership tests.

The undo is the whole trick

The two classic bugs, both silent and both common:

1. Forgetting the undo. After exploring a branch, path.pop() must run — and in grid problems like Word Search, the un-marking of the cell (grid[r][c] = ch after temporarily setting it to "#") is the same undo in disguise. Skip it and sibling branches see a corrupted state: cells still "visited," choices still "taken."
2. Recording the live path. results.append(path) stores a reference to the one shared list; every later mutation rewrites your saved answers, and you end up with N copies of the final (empty) path. Always append a copy: path[:] or list(path).

Recognizing it, and what it costs

The signal phrase is "all possible" — generate all subsets, all permutations, all valid IP splits, all board placements — combined with a small n, roughly n ≤ 20. That bound is not style; it is arithmetic. Backtracking is exponential by nature: 2^n subsets, n! permutations, and copying each result adds a factor of n, giving O(n · 2^n) and O(n · n!) totals. At n = 20, 2^20 is about a million — fine. At n = 40 it is a trillion — hopeless.

The counter-signal: if the problem only asks to count the ways and n is large, it wants dynamic programming, which shares subproblems instead of enumerating every solution. Backtracking is for when the answers themselves must be produced.