Backtracking (Try, Recurse, Undo)

Backtracking is how you systematically explore all possibilities — generate every subset, every permutation, or solve a puzzle with constraints. It sounds scary but it’s one small recursive template plus the idea of undoing a choice.

The idea

Think of every decision as a branch in a tree. Backtracking walks this tree depth-first: at each node you make a choice, recurse to explore the consequences, then undo the choice (backtrack) and try the next one. The undo is the whole trick — it lets one path variable be reused across all branches instead of copying state everywhere.

def backtrack(path, choices):
    if is_complete(path):
        record(path)                 # found a solution
        return
    for choice in choices:
        if not valid(choice): continue   # PRUNE
        path.append(choice)          # make the choice
        backtrack(path, remaining)   # recurse
        path.pop()                   # UNDO (backtrack) — the key line

Worked examples: subsets, permutations, combinations

Subsets — at each index, choose to include later elements (a start index avoids duplicates):

def subsets(nums):
    res = []
    def bt(start, path):
        res.append(path[:])              # every node is a subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1, path)              # i+1: don't reuse earlier elements
            path.pop()
    bt(0, [])
    return res
# subsets([1,2,3]) -> 8 subsets, including [], [1], [1,2], [1,2,3], ...

Permutations — order matters, so track which elements are used:

def permutations(nums):
    res = []
    def bt(path, used):
        if len(path) == len(nums):
            res.append(path[:]); return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True; path.append(nums[i])
            bt(path, used)
            path.pop(); used[i] = False
    bt([], [False] * len(nums))
    return res
# permutations([1,2,3]) -> 6 permutations

The difference between subsets, combinations and permutations is tiny — a start index (don’t reuse earlier), a target length, or a used set. Learn the shape; the variations are small.

Pruning: the thing that makes it practical

Backtracking is exponential, so the art is cutting branches early — skip choices that cannot possibly lead to a valid answer. In N-queens, never place a queen in an already-attacked column or diagonal:

def total_n_queens(n):
    cols, d1, d2 = set(), set(), set()
    count = 0
    def bt(r):
        nonlocal count
        if r == n: count += 1; return
        for c in range(n):
            if c in cols or (r-c) in d1 or (r+c) in d2:
                continue                     # PRUNE: attacked
            cols.add(c); d1.add(r-c); d2.add(r+c)
            bt(r + 1)
            cols.discard(c); d1.discard(r-c); d2.discard(r+c)   # undo
    bt(0)
    return count
# total_n_queens(4) -> 2

Good pruning turns an astronomically large tree into a small, feasible one — it’s the difference between a solution that runs and one that times out.

Step-by-step walkthrough

Trace Subsets of [1, 2, 3]. Each call records the current path, then tries each remaining element: add it, recurse, then pop it off before trying the next. Rows are in the order the calls happen.

All 2³ = 8 subsets appear, each exactly once. The start index stops us reusing earlier elements (so [2, 1] is never generated), and the pop() is what lets one path list serve every branch.

When to reach for it

Signals: “generate all …” (subsets, permutations, combinations, parentheses), “find all solutions”, or a constraint-satisfaction puzzle (N-queens, sudoku, word search). And remember the Big-O tell from Lesson 2: n ≤ ~20 in the constraints strongly hints at backtracking / exponential search.

Pitfalls

• Forgetting to undo. The path.pop() (and undoing any used/sets) is mandatory — without it, branches contaminate each other. This is the backtracking bug.
• Appending the live list instead of a copy. Record path[:] (a copy), not path, or every recorded solution ends up mutated/empty.
• No pruning. Without cutting dead branches, even small inputs explode. Always ask: can I reject this choice early?

Recap

Backtracking explores all choices as a decision tree: choose → recurse → undo. One template generates subsets, permutations, combinations (the variations are just a start index, a length, or a used set) and solves constraint puzzles. Pruning (rejecting invalid choices early) is what makes it feasible. It’s exponential, so n ≤ 20 is the signal. Always undo and record copies.

Practice: 12 solved problems on backtracking → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 16 — Graphs.