Backtracking Framework

Backtracking is a general algorithmic schema for incrementally building candidate solutions, abandoning (“backtracking from”) a partial candidate the moment it cannot possibly be completed to a valid full solution. Mechanically it is a depth-first search over an implicit state-space tree whose nodes are partial candidates and whose edges are the act of extending a partial candidate by one more decision. The skeleton of every backtracking algorithm is the three-step loop choose → recurse → undo — and the undo step is what distinguishes backtracking from “pure” recursion: state is mutated on the way down so we don’t pay to copy it, then unmutated on the way up so the next branch sees a clean slate. Backtracking solves problems whose solution space is too big to enumerate (e.g., 2^n, n!) by pruning — declining to descend into branches that provably cannot contain a solution. Done right, the wall-clock cost is the size of the pruned tree, often dramatically smaller than the worst-case b^d (branching factor b, depth d). Done wrong — usually by forgetting to undo, by mutating shared lists at the leaves, or by not pruning — backtracking quietly degrades to brute-force enumeration.

1. Intuition — Walking a Maze with Breadcrumbs

Imagine you’re hunting for the exit of a maze.

1. At each junction you pick a direction and walk.
2. You drop a breadcrumb so you know where you came from.
3. If you hit a wall (a dead-end), you walk back to the previous junction, pick up the breadcrumb you dropped there, and try a different direction.
4. If every direction at a junction leads to a dead-end, you back up that junction’s breadcrumb and try yet another direction one level up.

The “drop breadcrumb / pick up breadcrumb” is the choose / undo pair. The “if a junction is dead-end, back up” is the prune step. The “try a different direction” is the loop over choices. That’s the entire framework, transposed onto a maze.

What makes backtracking efficient compared to enumerating all possible maze paths is that you recognise dead-ends early — you don’t keep walking once you’ve hit a wall. In algorithm terms: you check a constraint before committing to a child branch and, if violated, you skip the subtree entirely.

2. Tiny Worked Example — Permutations of [1, 2, 3]

We will generate all 3! = 6 permutations of {1, 2, 3} and trace the state-space tree by hand.

The state we maintain is two pieces:

• path — the partial permutation built so far,
• used — a boolean array marking which numbers are already in path.

Tracing:

backtrack( path=[], used=[F,F,F] )
├── choose 1 → path=[1], used=[T,F,F]
│   ├── choose 2 → path=[1,2], used=[T,T,F]
│   │   └── choose 3 → path=[1,2,3], used=[T,T,T]   ← record [1,2,3]
│   │       └── undo 3 → path=[1,2], used=[T,T,F]
│   │   └── undo 2 → path=[1], used=[T,F,F]
│   └── choose 3 → path=[1,3], used=[T,F,T]
│       └── choose 2 → path=[1,3,2], used=[T,T,T]   ← record [1,3,2]
│           └── undo 2 → path=[1,3], used=[T,F,T]
│       └── undo 3 → path=[1], used=[T,F,F]
│   └── undo 1 → path=[], used=[F,F,F]
├── choose 2 → path=[2], used=[F,T,F]
│   ├── choose 1 → path=[2,1], ... → record [2,1,3]
│   ├── choose 3 → path=[2,3], ... → record [2,3,1]
│   └── undo 2
└── choose 3 → path=[3], used=[F,F,T]
    ├── choose 1 → path=[3,1], ... → record [3,1,2]
    ├── choose 2 → path=[3,2], ... → record [3,2,1]
    └── undo 3

Six leaves → six recorded permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. Total internal nodes visited: roughly 1 + 3 + 3·2 + 3·2·1 = 16 — i.e., we walk a tree, not a flat list.

Notice the shape of the recursion: the algorithm reuses one shared path list and one shared used array. After each choose we recurse, then undo to restore the state for the next iteration of the loop. There is no copying. This is what gives backtracking its O(depth) memory rather than O(states).

3. The Canonical Pseudocode

backtrack(state):
    if is_solution(state):
        record(state)                  # could be: emit / collect / stop
        return                         # or 'return True' if you only need one
    for choice in choices(state):
        if not valid(choice, state):
            continue                   # prune: skip this branch
        apply(choice, state)           # CHOOSE  (mutate)
        backtrack(state)               # RECURSE
        undo(choice, state)            # UNDO    (un-mutate; matched pair)

Five named primitives:

Primitive	What it does	When the cost lives
is_solution(state)	Predicate: is state a complete, valid solution?	Inner of recursion; called at every node
choices(state)	Generates the children of state (the next decisions)	Called at every internal node
valid(choice, state)	Prune: can extending state by choice possibly lead to a solution?	Called at every edge; the heart of efficiency
apply(choice, state)	Mutate state to reflect the chosen extension	Constant or near-constant per call
undo(choice, state)	The exact inverse of apply; restores state	Constant or near-constant per call

Two non-negotiable invariants:

• undo exactly inverts apply. Whatever fields apply modified, undo must restore. If apply does path.append(x); used[x] = True; sum += x, then undo does path.pop(); used[x] = False; sum -= x. Asymmetric apply/undo is the #1 source of backtracking bugs.
• valid is sound (no false rejects). If valid returns False, the subtree under that choice must truly contain no solution. A buggy valid that returns False for a viable branch turns into an incorrect algorithm, not just a slow one.

4. Python Implementation — Generic Skeleton plus Concrete Instances

4.1 The skeleton

def backtrack(state, results):
    if is_solution(state):
        results.append(snapshot(state))   # IMPORTANT: copy, not reference
        return
    for choice in choices(state):
        if not valid(choice, state):
            continue
        apply(choice, state)              # CHOOSE
        backtrack(state, results)         # RECURSE
        undo(choice, state)               # UNDO

The single most common bug at the leaf line is appending state directly:

results.append(state)        # WRONG — every result aliases the same mutable object
results.append(state[:])     # right — shallow copy of a list
results.append(snapshot(state))  # right — explicit deep copy if state is nested

Because the skeleton mutates a shared state, by the time the outer loop terminates every reference in results would point at the empty post-undo state. This is the same gotcha as Python’s mutable-default-argument trap — discussed in §10.

4.2 Permutations

def permutations(nums: list[int]) -> list[list[int]]:
    results = []
    path = []
    used = [False] * len(nums)
 
    def backtrack():
        if len(path) == len(nums):       # is_solution
            results.append(path[:])      # snapshot copy
            return
        for i in range(len(nums)):       # choices
            if used[i]:                  # valid (skip if already used)
                continue
            path.append(nums[i]);  used[i] = True   # apply
            backtrack()                              # recurse
            path.pop();            used[i] = False  # undo (mirror image)
 
    backtrack()
    return results

See Permutations for the deep dive (in-place swap variant, Heap’s algorithm, lex next-permutation).

4.3 N-Queens (sketch — full note: N-Queens)

def solve_n_queens(n: int) -> list[list[str]]:
    results = []
    cols = [False] * n
    diag1 = [False] * (2 * n - 1)        # row + col  (anti-diagonal)
    diag2 = [False] * (2 * n - 1)        # row - col + (n-1) (main diagonal)
    queens = []                          # column index per row
 
    def backtrack(row):
        if row == n:
            results.append(render(queens))
            return
        for col in range(n):
            if cols[col] or diag1[row + col] or diag2[row - col + n - 1]:
                continue                  # prune: same column or diagonal
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = True
            queens.append(col)
            backtrack(row + 1)
            queens.pop()
            cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False
 
    backtrack(0)
    return results

The efficiency of N-queens comes from the three boolean arrays — checking “this square attacks an existing queen” in O(1) instead of scanning. Without that pruning, the algorithm walks the full n^n tree of placements; with it, the actual tree visited for n = 8 is small enough to enumerate by hand.

5. Why O(depth) Memory, Not O(states)

Naive enumeration of “all subsets of n elements” allocates one list per leaf — 2^n lists, total Θ(n · 2^n) memory. Backtracking allocates one shared path that grows and shrinks. At any instant the live state is the current root-to-leaf walk plus the call stack.

Quantity	Naive enumeration	Backtracking
States visited	O(b^d)	O(b^d) (same — the algorithm walks the same tree)
Solutions emitted	up to b^d	up to b^d
Live memory at any instant	O(b^d) (all states stored)	O(d) (one root-to-leaf walk)
Recursion stack depth	O(d)	O(d)

The asymptotic time is identical to enumeration (you still visit every node of the unpruned tree), but memory is exponentially smaller. This is what lets backtracking solve n = 30 subset problems on a laptop where storing all 2^30 ≈ 10^9 lists explicitly would not fit. The trade-off is that you produce results lazily, one at a time, rather than as a single returned collection (and if your caller stores them all anyway, you’ve recovered the O(b^d) total memory at the output boundary, but the intermediate computation is still cheap).

6. Pruning Strategies — The Real Source of Speedup

A backtracking schema with no pruning is just brute-force enumeration. The art is in pruning.

6.1 Constraint Propagation

When a partial state forces a downstream variable’s value, propagate the implication immediately rather than waiting for the loop to discover it via failure. Sudoku is the canonical example: if a row already has 8 filled cells, the 9th cell’s value is forced — propagate before recursing. Constraint propagation can shrink the search tree by orders of magnitude. (Russell & Norvig Ch. 6 has the formal CSP treatment.)

6.2 Bound-Based Pruning (Branch and Bound)

If the optimal solution must have value at most B and the best possible completion of the current partial state is provably worse than B, abandon the branch. This is the spine of TSP solvers, knapsack solvers, and many integer-programming algorithms — pure backtracking augmented with a lower bound function. The bound need only be admissible (never over-promising) for correctness; tighter bounds prune more.

6.3 Symmetry Breaking

Many problems have a symmetry group under which solutions are equivalent. N-queens placement is symmetric under board rotation and reflection: of the 92 solutions for n = 8, only 12 are unique up to symmetry. By committing the first queen to a fixed half of the board (e.g., column ≤ ⌈n/2⌉), the search space is roughly halved. The trick is generic: if your problem has a symmetry that fixes a coordinate to a canonical orientation, applying that constraint is a free 2× to k× speedup.

6.4 Ordering — Most-Constrained Variable First

When you have a choice of which decision to make next (e.g., which empty cell of a sudoku to fill), pick the most constrained one first — the variable with the fewest legal values. This reduces the branching factor at the top of the tree, where pruning matters most. Heuristic name: MRV (Minimum Remaining Values). The dual heuristic, least-constraining value, picks the value (within a chosen variable) that rules out the fewest options downstream.

6.5 Memoization for Subset-State Backtracking

Some backtracking problems revisit the same partial state via different paths. If state is hashable and small (e.g., a bitmask of visited cities in TSP), memoizing f(state) turns exponential search into bitmask DP. The line between “backtracking with memoization” and “DP over subsets” is fuzzy — they are two presentations of the same algorithm.

7. Backtracking vs Depth-First Search — What’s Different?

DFS is the underlying control flow. Backtracking is DFS with two additional commitments:

1. The graph is implicit. The state-space tree is not stored anywhere — children are generated on demand by choices(). (DFS on an explicit graph stores the adjacency list.)
2. State is mutated and undone, not copied. DFS on a fixed graph just maintains a visited set; backtracking is pushing and popping multiple coordinated state fields per recursive call.

A DFS that explicitly enumerates all root-to-leaf paths in a tree and copies the path at every recursion level is conceptually backtracking but loses the memory benefit. A DFS that mutates a shared “current path” array and undoes on return is backtracking. The mechanism is the same; the discipline (mutate-then-undo) is what makes it backtracking.

8. Correct vs Broken — Side-by-Side

The most pernicious backtracking bugs are silent: the algorithm “works” on small inputs and produces nonsense on larger ones. Below is the canonical correct/broken pair for permutation generation.

8.1 Correct

def permutations(nums):
    results, path, used = [], [], [False] * len(nums)
    def go():
        if len(path) == len(nums):
            results.append(path[:])      # ✓ snapshot copy
            return
        for i in range(len(nums)):
            if used[i]: continue
            path.append(nums[i]); used[i] = True   # ✓ apply
            go()
            path.pop();           used[i] = False  # ✓ undo (both fields)
    go()
    return results

8.2 Broken — appended reference instead of copy

def permutations_broken_1(nums):
    results, path, used = [], [], [False] * len(nums)
    def go():
        if len(path) == len(nums):
            results.append(path)         # ✗ appends the reference!
            return
        for i in range(len(nums)):
            if used[i]: continue
            path.append(nums[i]); used[i] = True
            go()
            path.pop();           used[i] = False
    go()
    return results
# ⇒ returns [[], [], [], [], [], []]  — every entry aliases the same path that ends up empty

8.3 Broken — forgot to undo used[i]

def permutations_broken_2(nums):
    results, path, used = [], [], [False] * len(nums)
    def go():
        if len(path) == len(nums):
            results.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]: continue
            path.append(nums[i]); used[i] = True
            go()
            path.pop()                    # ✗ undid path but not used!
            # used[i] = False  ← missing
    go()
    return results
# ⇒ returns only [[1, 2, 3]]  — the first leaf — because used[i] is never reset

8.4 Broken — undo runs outside the loop

def permutations_broken_3(nums):
    results, path, used = [], [], [False] * len(nums)
    def go():
        if len(path) == len(nums):
            results.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]: continue
            path.append(nums[i]); used[i] = True
            go()
        # ✗ undo placed after the loop — runs once instead of per iteration
        if path:
            x = path.pop()
            used[nums.index(x)] = False
    go()
    return results
# ⇒ wrong output, depending on data; the undo must mirror the apply per-iteration

The pattern is uniform: apply and undo must be paired siblings of the recursive call inside the loop, not floated outside it. The pseudocode shape

apply
recurse
undo

is the only correct arrangement.

9. Complexity — Branching Factor × Depth

Let b be the maximum branching factor (max size of choices(state)) and d the maximum recursion depth. Then:

• States visited (no pruning): O(b^d).
• Time per state: the cost of choices, valid, apply, undo, plus the leaf-level record. Often O(d) for record (snapshot copy of a length-d path) and O(1) or O(d) for the others.
• Total time (no pruning): roughly O(d · b^d) if the leaf record is O(d); O(b^d) if leaves cost O(1).
• Memory: O(d) for the recursion stack and shared mutable state (excluding the output collection).

With effective pruning the actual tree visited is much smaller, but worst-case bounds are stated for the unpruned tree because we generally cannot prove tighter bounds without a problem-specific argument.

For the four sibling notes:

Problem	b	d	Tree size	Per-leaf cost	Total time
Permutations of n items	n	n	n! (with the “used” prune)	O(n) snapshot	O(n · n!)
Combinations C(n, k)	up to n − d	k	C(n, k) (with start-index prune)	O(k) snapshot	O(k · C(n, k))
Subsets of n items	2 (include/exclude)	n	2^n	O(n) snapshot	O(n · 2^n)
N-queens (n queens)	up to n	n	empirically tiny w/ diagonal pruning	O(n) render	varies

The n · ... factor accounts for the snapshot copy at each leaf — the recursion proper visits n! (or C(n, k), or 2^n) leaves but each costs O(n) to record.

10. Pitfalls

1. Forgetting to undo state changes on return. The single most common backtracking bug. Every mutation that apply performs must be reversed by undo. If apply modifies three fields, undo must reverse three fields. Even one missed field corrupts later branches. (See §8.3 — used[i] not reset.)
2. Mutable default argument def f(x, acc=[]):. Python evaluates default arguments once at function definition. The acc=[] is shared across calls — every recursion accumulates into the same list. Always use acc=None and acc = [] if acc is None else acc inside, or pass an explicit [] per call. This bug is closely related to backtracking because backtracking depends on shared mutable state and the default-arg gotcha can bleed into adjacent code.
3. results.append(path) instead of results.append(path[:]) (or deep copy). The leaf snapshot must be a copy of the current state, not a reference. Without the copy, every recorded “result” aliases the same list, which by end-of-traversal is empty. (See §8.2.)
4. Snapshot is shallow when state is nested. path[:] copies the outer list. If path contains lists (e.g., a list of tuples representing N-queens rows), the inner lists are still shared. Use copy.deepcopy(state) or build the snapshot from primitives.
5. Doing the prune check after applying the change. The order is valid(choice, state) → apply → recurse → undo, not apply → valid → maybe undo. Applying first means you may need an extra undo on the prune branch — easy to forget and asymmetric.
6. Pruning that’s too aggressive. A buggy valid that returns False for viable branches makes the algorithm incorrect, not just slow. Test pruning with and against a known-good brute-force enumeration on small inputs.
7. Pruning that’s too weak / missing. A schema with no pruning is brute force, even if you call it backtracking. Investing in a sharper valid (or a bound function for branch-and-bound) is usually the highest-leverage optimisation.
8. Recursion depth limit. Python defaults to sys.setrecursionlimit(1000). For n = 1000 permutation problems you’d hit it. Either lift the limit (sys.setrecursionlimit(10**6)) or convert to an iterative explicit-stack version. The iterative version keeps the same O(depth) memory profile but exposes the apply/undo pairing in the stack frame.
9. Not handling duplicates correctly. If the input contains duplicates and you want each distinct result once, the standard trick is sort the input + skip duplicates at the same recursion level: if i > start and nums[i] == nums[i-1]: continue after sorting nums. Skipping at the same level is the key — duplicates across different recursion levels are part of distinct partial paths and must not be skipped. See Permutations §X (LC 47), Combinations (LC 40), Subsets (LC 90) for full discussion.
10. Confusing branching factor with depth. b^d, not b · d or b + d. A backtracker over n items with n choices at each level has n^n worst-case nodes (without the “used” prune); with the “used” prune (each item used once) it has n!. The pruning matters.
11. Letting the recursive function depend on outer-scope state implicitly without realising it. Python closures bind by reference. Mutating an outer list from inside a recursive nested function works (it’s how the skeleton above is written); reassigning a primitive (x = 0 then x += 1 inside) creates a local. Use nonlocal x or wrap in a one-element list if you need to mutate a scalar across recursion levels.
12. Returning early on first solution when you wanted all solutions. record(state); return may or may not abort the search depending on what you want. For “find any solution” return a sentinel up the stack and have callers check it. For “find all” never short-circuit.

11. Diagram — A Generic State-Space Tree

flowchart TD
    R["root: state₀ (empty partial)"]
    R --> A["apply choice c1<br/>state = state₀ ⊕ c1"]
    R --> B["apply choice c2<br/>state = state₀ ⊕ c2 (PRUNED — invalid)"]
    R --> C["apply choice c3<br/>state = state₀ ⊕ c3"]
    A --> AA["c1 → c1.1<br/>...complete: record"]
    A --> AB["c1 → c1.2<br/>(PRUNED)"]
    A --> AC["c1 → c1.3<br/>...complete: record"]
    C --> CA["c3 → c3.1<br/>(dead-end deeper)"]
    C --> CB["c3 → c3.2<br/>...complete: record"]

    style B stroke-dasharray: 5 5,stroke:#a33
    style AB stroke-dasharray: 5 5,stroke:#a33
    style CA stroke-dasharray: 5 5,stroke:#a33

What this diagram shows. Each node is a partial candidate solution; each edge is the act of apply-ing one more choice (and its dual undo on the way back up the recursion). Solid nodes are visited and either lead to recorded solutions (leaves marked “record”) or extend further. Dashed nodes/edges are pruned by valid() — those subtrees are never traversed. The right-hand subtree under c3 shows pruning saving work mid-tree: c3.1 is reachable, the algorithm descends, finds a dead-end deeper down (no valid grandchildren), backs up via undo, and tries c3.2 — which succeeds. The total work is the size of the visited (pruned) tree, not the size of the full tree of all possible decisions.

12. Common Interview Problems

Problem	LeetCode	Subdomain	Note
Permutations	46	Order matters, all elements used	Permutations
Permutations II (with duplicates)	47	Same + dedupe at same level	Permutations
Combinations	77	Choose k of n, order doesn’t matter	Combinations
Combination Sum	39	Like 77, target sum, repeats allowed	Combinations
Combination Sum II (with duplicates)	40	Sort + dedupe at same level	Combinations
Subsets	78	Power set	Subsets
Subsets II (with duplicates)	90	Sort + dedupe at same level	Subsets
Letter Combinations of Phone Number	17	Cartesian product, simple state	Backtracking-101
Generate Parentheses	22	Pruning by open ≥ close invariant	Generate Parentheses
N-Queens	51	Constraint diagonal/column pruning	N-Queens
Sudoku Solver	37	Constraint propagation; row/col/box bitmasks	Sudoku Solver
Word Search	79	Grid DFS with visited un-mark on return	Word Search
Restore IP Addresses	93	Length and value constraints per segment	Backtracking-classic
Palindrome Partitioning	131	valid = “is prefix a palindrome?”	Backtracking-classic

13. Open Questions

• When does converting backtracking to iterative DP (memoization on state) win? Roughly: when the same state is reachable via many paths and the state is small/hashable.
• Is there a principled way to choose between MRV ordering and “natural” left-to-right ordering when both are admissible? The literature suggests MRV is usually a big win for CSPs but adds bookkeeping; for problems whose branching factor is uniform, MRV is overkill.
• How does Knuth’s “estimating the efficiency of backtrack programs” (1975) random-sample approach work in practice for predicting the runtime of a backtracker before running it? (Cited as one of the few principled answers to “how long will this take?”)

14. See Also

• Depth-First Search — backtracking is DFS over an implicit state-space tree
• Recursion vs Iteration — backtracking is presented recursively but can be made iterative
• Permutations, Combinations, Subsets — three canonical generation problems built on this skeleton
• N-Queens, Sudoku Solver, Word Search, Generate Parentheses — classic constraint-pruning instances
• Bitmask DP — what backtracking-with-memoization becomes when state collapses to a hashable mask
• Master Theorem — does not apply directly (state-space size is b^d, not a master-theorem recurrence) but the recursion-tree intuition transfers
• Big-O Notation, Big-Omega and Big-Theta
• SWE Interview Preparation MOC