4.18.0 — Backtracking: The Pattern

Recognition cue. The problem says all, every, generate, enumerate, or asks for combinations, permutations, subsets, partitions, or arrangements. The constraint is small — n up to about 20 for subsets, up to about 10 for permutations — which is the setter telling you an exponential answer is expected.

The move. Build a partial answer one choice at a time. When it is complete, record it. When it cannot possibly work, abandon it. Undo each choice on the way back out.

What backtracking actually is

It is depth-first search over a tree that you never build. The tree exists only as the sequence of calls on the stack.

Each node of that imaginary tree is a partial answer. Each edge is one choice. A leaf is either a complete answer or a dead end.

                  []
        /                    \
      [1]                     []          ← choose 1, or do not
     /    \                 /    \
  [1,2]   [1]            [2]      []
   / \     / \           /  \     /  \
[1,2,3][1,2][1,3][1]  [2,3][2] [3]  []   ← eight subsets of {1,2,3}

Once you see the tree, every problem in this chapter is the question what are the branches at each node, and which ones can I refuse to walk down?

The four parts

Every backtracking solution has exactly these, in this order. Write them as four separate thoughts.

def backtrack(state):
    if is_complete(state):          # 1. BASE CASE
        record(state)
        return

    for choice in choices(state):   # 2. THE CHOICES
        if not allowed(choice):     # 3. THE CONSTRAINT — this is the pruning
            continue
        make(choice)                # 4a. do it
        backtrack(state)            #     recurse
        undo(choice)                # 4b. UNDO — the "backtracking"

Part 3 is where all the performance is. Checking validity as you choose prunes an entire subtree. Checking it only on complete answers is brute force wearing a recursion costume, and it is the difference between 8^8 and about 2,000 in N-Queens.

Part 4b is where all the correctness is. Whatever you add before recursing must be removed after. Forget it and state leaks between branches, and the results are quietly wrong.

The three loop shapes, and how to choose

This is the decision that confuses people most, so here it is in one place. What differs between problems is only the choices available at each node.

Shape 1 — include or exclude (subsets)

At index i, either take nums[i] or do not. Then move to i + 1.

def backtrack(i, path):
    if i == len(nums):
        result.append(path[:])      # copy!
        return
    path.append(nums[i])            # take it
    backtrack(i + 1, path)
    path.pop()                      # undo
    backtrack(i + 1, path)          # skip it

Two branches per node, n levels deep → 2^n leaves. Use when each element is independently in or out.

Shape 2 — choose the next element, moving forward (combinations)

A loop from a start index, and the recursive call moves the start forward. Order does not matter, so [1,2] and [2,1] are the same answer and only one is generated.

def backtrack(start, path):
    result.append(path[:])          # every node is an answer, for subsets
    for i in range(start, len(nums)):
        path.append(nums[i])
        backtrack(i + 1, path)      # i + 1: never look back
        path.pop()

i + 1 versus i is the whole difference between two problem families. i + 1 means each element is used at most once. Passing i means it can be reused — that is Combination Sum.

Shape 3 — choose any unused element (permutations)

A loop over everything, with a used-marker. Order matters, so [1,2] and [2,1] are both answers.

def backtrack(path, used):
    if len(path) == len(nums):
        result.append(path[:])
        return
    for i in range(len(nums)):
        if used[i]: continue
        used[i] = True
        path.append(nums[i])
        backtrack(path, used)
        path.pop()
        used[i] = False

n choices, then n−1, then n−2 → n! leaves.

The decision, in one table

the problem wants	order matters?	reuse allowed?	shape
subsets	no	no	1 or 2
combinations	no	no	2, recurse with i + 1
combination sum	no	yes	2, recurse with i
permutations	yes	no	3, with a used array

Duplicates: the one rule

When the input contains repeated values, you will generate the same answer twice. Sort first, then skip a value that equals its predecessor at the same level of the tree:

nums.sort()
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i - 1]:
        continue                    # a sibling already tried this value

i > start, not i > 0. The guard must skip duplicates among siblings — different choices at the same position — not duplicates along the path. Using i > 0 would wrongly forbid [2, 2] when there really are two 2s available.

Say that condition out loud when you write it. It is the single most-missed detail in this chapter.

Copy the result

result.append(path[:])      # a copy — NOT result.append(path)

path is one shared list that keeps changing. Appending it without copying stores a reference, and by the end every entry in result is the same empty list. In JavaScript, [...path].

This bug produces output that looks structurally right and is entirely wrong, so it is worth checking every time.

Complexity, honestly

You cannot beat the size of the output. If a problem asks for all 2^n subsets, the answer alone is exponential.

So the complexity is roughly (number of results) × (cost of building each one):

• subsets — O(2^n \times n)
• permutations — O(n! \times n)
• combination sum — bounded by the tree size, hard to state exactly, and saying so honestly is better than inventing a formula

Pruning does not change the asymptotic bound — it changes the constant, and the constant is everything. N-Queens without pruning tries 8^8 \approx 16.7 million placements; with column and diagonal checks at the moment of placing, it explores about 2,000.

The nine problems

#	Problem	Shape	The one insight
4.18.1	Subsets ★	1 or 2	Every node of the tree is an answer
4.18.2	Combination Sum ★	2, reuse	Recurse with i, not i + 1
4.18.3	Permutations ★	3	A used-marker instead of a start index
4.18.4	Subsets II	2	Sort, then skip siblings with i > start
4.18.5	Combination Sum II	2	The duplicate skip and i + 1 together
4.18.6	Word Search ★	grid	The board itself is the visited set
4.18.7	Palindrome Partitioning ★	2	The choice is where to cut
4.18.8	Letter Combinations ★	per-position	The branching factor comes from a lookup table
4.18.9	N-Queens	per-row	Name the conflict groups: column, r−c, r+c

★ marks the Blind 75 subset.

The traps on this pattern

Forgetting to copy the result. Every entry ends up identical.

Forgetting the undo. State leaks between branches.

i > 0 instead of i > start in the duplicate skip. It removes legitimate answers.

Checking validity only at the leaves. That is brute force. Check at the moment of choosing.

Passing i + 1 when reuse is allowed, or i when it is not. One character, two completely different problems.

Not sorting before the duplicate skip. The skip only works if equal values are adjacent.

What the interviewer will push on

"Walk me through your recursion tree for n = 3." Draw it. If you cannot draw it, the code will not be right.

"Where does the pruning happen?" Point at the constraint check and say what subtree it removes.

"What is the complexity?" The output size times the cost per result, and then say that pruning changes the constant rather than the exponent.

"Why i + 1 here and i there?" Reuse allowed or not.

"How do you avoid duplicate answers?" Sort, then skip equal siblings with i > start.

"Could you do it iteratively?" For subsets, yes — start with [[]] and for each element append copies of everything so far with that element added. For the rest, an explicit stack of states, which is messier than the recursion.

One thing to volunteer: name the four parts as you write them — choices, constraint, recurse, undo — and say which of the three shapes you picked and why. That framing is what makes the next backtracking problem easy instead of a fresh puzzle.

Recall

• Backtracking is DFS over a tree you never build. Each node is a partial answer; each edge is one choice.
• Four parts: base case · the choices · the constraint (this is the pruning) · make, recurse, undo.
• Three shapes: include/exclude · loop from a start index (order does not matter) · loop over all with a used-marker (order matters).
• i + 1 = each element used once. i = reuse allowed. One character apart, two problem families.
• Duplicates: sort first, then if i > start and nums[i] == nums[i-1]: continue. It is i > start, not i > 0.
• Copy the path when recording: path[:] or [...path]. Otherwise every result is the same reference.
• Complexity is output size × cost per result. Pruning changes the constant, not the exponent — and the constant is everything.

Next: 4.18.1 Subsets — the simplest tree in the chapter, and the one to draw before writing anything.