Backtracking

Type: Algorithm Paradigm | LeetCode problems: 200+

---

Core Concepts

State space tree — the implicit tree of all possible candidates, where each node is a partial solution and each edge is one choice. Backtracking performs DFS on this tree without materialising it in memory.

Candidate / partial solution — the sequence of choices made so far. A candidate is extended one step at a time and abandoned the moment it violates a constraint.

Choice point — a position in the search where multiple options are available. The algorithm branches at each choice point, tries one option, recurses, then tries the next.

Constraint — a condition that every valid solution must satisfy. Checking constraints early and abandoning invalid branches (pruning) is what separates efficient backtracking from brute-force enumeration.

Goal test — the check that determines whether the current candidate is a complete, valid solution. Triggered when no more choices remain (or when the candidate reaches a target depth/length).

Pruning — cutting a branch of the search tree without exploring it, by proving that no complete solution can extend the current candidate. Pruning correctness is the main source of bugs; a valid branch must never be cut.

Undo / restore — after returning from a recursive call, all state changes made during that call must be reversed so the parent call sees the original state. This is the defining mechanic of backtracking and the most common source of bugs.

Choose-explore-unchoose (CEU) template — the canonical three-phase structure: make a choice (extend the candidate), recurse (explore all extensions), undo the choice (restore state). Every backtracking problem maps to this template.

---

Types / Variants

---

Key Algorithms

Subset Enumeration

Generate all 2ⁿ subsets of an array. At each index, make two choices: include the element or skip it, then recurse on the remaining elements. O(n · 2ⁿ) time (copying each subset), O(n) stack depth.

Key insight: the binary include/skip decision at every index produces every subset exactly once without needing a start-index parameter.

Combination Enumeration (size k, no duplicates in input)

Select exactly k elements from n, each index used at most once. Pass a start index and iterate from start to n−k+remaining (pruning when fewer elements remain than needed). O(C(n,k) · k) time.

Key insight: iterating forward from start — never backward — prevents reordering the same elements into a "different" combination.

Combination Sum (elements reusable, distinct values)

Select elements (with repetition) that sum to a target. Pass the same index when recursing (allows reuse); subtract from target as you go; prune when target < 0. O(target/min_val ^ n) worst case, heavily pruned in practice.

Combination Sum II (duplicates in input, each element used once)

Sort the input. Use a start index. At each level, skip nums[i] if i > start and nums[i] == nums[i-1] — this prevents choosing the same value twice at the same recursion level while still allowing it at different levels.

if i > start and nums[i] == nums[i - 1]:
    continue

Permutation Enumeration

Generate all n! orderings. Maintain a used boolean array; at each position iterate all unused elements, mark, recurse, unmark. O(n · n!) time.

Alternative — in-place swap: swap index start with each index ≥ start, recurse, swap back. Avoids the extra array but generates permutations in a different order.

Permutations II (duplicates in input)

Sort the input. In the swap-free variant, skip nums[i] when not used[i] is true but also used[i-1] is false and nums[i] == nums[i-1] — this enforces that among equal elements, only the leftmost unused one may be chosen at each level.

if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
    continue

N-Queens

Place n queens on an n×n board so no two share a row, column, or diagonal. Assign one queen per row (rows are implicit levels); at each row iterate columns; prune if column or diagonal is already occupied. Track three sets: cols, diag1 (row−col), diag2 (row+col). O(n!) time upper bound, heavily pruned.

Key insight: the difference row − col is constant along any \ diagonal; the sum row + col is constant along any / diagonal.

Sudoku Solver

Fill a 9×9 grid. Scan for the next empty cell; try digits 1–9; prune if any digit violates row, column, or 3×3-box constraints. Recurse; if no digit works, return false (backtrack). O(9^(empty cells)) worst case, heavily pruned.

Key insight: instead of trying cells in raster order, choosing the cell with the fewest valid digits first (minimum remaining values heuristic) can reduce the search dramatically — though the plain raster-order approach passes all LeetCode tests.

Word Search (2D grid)

Given a 2D grid of characters and a target word, find if a path of adjacent cells spells the word. DFS from every cell; mark visited by replacing grid[r][c] with '#'; restore after recursion. O(m · n · 4^L) time where L is word length.

Key insight: in-place marking avoids an O(mn) visited set; the restore step is the backtrack.

Palindrome Partitioning

Partition a string into all substrings that are each palindromes. At each position, iterate all end indices; if s[start:end+1] is a palindrome, recurse from end+1. O(n · 2ⁿ) time; precompute palindrome check with a 2D DP table to drop to O(2ⁿ) per subproblem.

Generate Parentheses

Generate all strings of n pairs of balanced parentheses. At each step, add ( if open < n or ) if close < open. No explicit undo needed because strings are immutable (Python concatenation creates a new object). O(Cₙ) time where Cₙ is the nth Catalan number.

Letter Combinations of a Phone Number

For each digit, branch over its mapped letters; recurse on the next digit. O(4^n · n) time. Classic multi-branch-per-level backtracking.

---

Advanced Techniques

Pruning by Sorting + Duplicate Skip

Solves: enumeration problems where the input contains duplicate values and the output must contain only distinct results.
Mechanism: sort the input once before backtracking; at each recursion level, skip nums[i] when i > start and nums[i] == nums[i-1]. This skips duplicates at the same depth without needing a set to deduplicate results afterward.
When to prefer over alternatives: always prefer over post-hoc deduplication with a set — it avoids generating duplicates at all, reducing both time and memory. Use a result set only when sorting would change the semantics (e.g., strings with different orderings that are semantically different).
Complexity: same asymptotic as without deduplication; constant-factor improvement in practice.

Feasibility Pruning (Early Constraint Checking)

Solves: any backtracking problem where partial candidates can be proven infeasible before they are fully extended.
Mechanism: check constraints on the candidate at every extension step, not only at the goal test. For sum problems: prune when remaining target < 0 (or > sum of remaining elements). For CSPs: check all affected constraints before placing a value.
When to prefer over alternatives: always add feasibility pruning when the constraint can be checked in O(1) or O(n) per step; the reduction in tree size usually far outweighs the per-node cost. Skip only when every extension of every partial candidate is valid (rare).
Complexity: same worst case; dramatically better average case; converts exponential trees into near-linear for well-constrained problems.

Memoization on Backtracking State (Backtracking → DP)

Solves: backtracking problems where the same partial state is reached via different choice sequences (overlapping subproblems).
Mechanism: convert the mutable path into a hashable state tuple; cache the result with @functools.cache or a dict. If the result at a given state is always the same regardless of how it was reached, memoization is valid.
When to prefer over alternatives: use when the number of distinct states is polynomial in the input size and states repeat frequently; remain with pure backtracking when the path history matters (i.e., the same state reached via different paths has different results) or when states are exponentially many and non-repeating.
Complexity: reduces from O(branches^depth) to O(states × branches) — often the difference between TLE and AC.

In-Place Grid Marking

Solves: grid path / word search problems where visited cells must be tracked.
Mechanism: replace grid[r][c] with a sentinel (e.g., '#') on entry, restore the original character on exit. Avoids allocating an O(mn) visited set or passing it through recursion.
When to prefer over alternatives: prefer when grid characters are non-sentinel values and restoring is safe. Use an explicit visited set when the grid must not be mutated or when multiple DFS calls share the grid simultaneously.
Complexity: O(1) mark/unmark vs. O(1) set operations — similar speed, but avoids allocation.

Bitmask State for Permutations

Solves: permutation problems where n ≤ 20 and the visited state must be hashable for memoization (e.g., Travelling Salesman, shortest Hamiltonian path).
Mechanism: encode which elements have been used as a bitmask integer. used | (1 << i) marks element i; used & (1 << i) checks it. The state (current_node, visited_mask) is hashable and enables memoization.
When to prefer over alternatives: only when n ≤ 20 (bitmask DP is O(2ⁿ · n²)). For larger n without memoization, use a plain visited[] array.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Shallow copy when appending to results. result.append(path) appends a reference; later mutations to path corrupt all saved results. Fix: result.append(path[:]) or result.append(path.copy()).

• Forgetting to undo state. A global or outer-scope variable mutated during a recursive call that is not restored causes sibling branches to see incorrect state. Every mutation must have a paired undo on every exit path, including early returns.

• Sibling-duplicate skip applied at wrong level. The condition i > start and nums[i] == nums[i-1] skips duplicates at the current recursion level. Writing i > 0 instead of i > start incorrectly skips valid placements at deeper levels.

• Using element at index i multiple times unintentionally. For once-each combinations, recurse with i+1; for reusable elements, recurse with i. Mixing these produces either missing or duplicate results.

• Off-by-one in combination pruning. The optimisation if i > n - remaining: break must account for whether indices are 0-based or 1-based and whether the end boundary is inclusive.

• Grid bounds check order. Always check 0 <= r < rows and 0 <= c < cols before accessing grid[r][c]; Python will not short-circuit the access if bounds come second.

• Grid marking not restored on early return. If a base-case check returns before the unmark line, the cell stays marked for sibling DFS calls. Put the unmark in a finally block or ensure every return path passes through the restore.

• Unsorted input with duplicate skip. The sibling-skip pattern only works when equal elements are adjacent. If input is not sorted, duplicates will not be adjacent and the skip condition silently fails, producing duplicate results.

• Permutation visited not reset. Using a module-level or outer-function visited list without resetting between top-level calls produces incorrect results in multi-test-case scenarios.

• Pruning that cuts valid branches. A pruning condition that is too aggressive (e.g., pruning on target <= 0 instead of target < 0 when target == 0 is a valid solution) silently drops correct answers. Verify pruning conditions against the goal test.

---

Implementation Notes

• path[:] is idiomatic Python for a shallow list copy; for nested structures use copy.deepcopy().
• Python's default recursion limit is 1000. For grids larger than ~30×30 or deep trees, add sys.setrecursionlimit(10000) or convert to an explicit stack.
• @functools.cache / @functools.lru_cache requires all arguments to be hashable. Lists and sets are not hashable; convert path to a tuple for memoized backtracking.
• functools.cache (Python 3.9+) is equivalent to lru_cache(maxsize=None) and is preferred for backtracking memoization where cache size is unbounded.
• Sorting with nums.sort() mutates the input array. If the caller must see the original order, sort a copy: nums = sorted(nums).
• For in-place grid marking, avoid sentinels that could appear as valid values in the input (e.g., use '#' only if the problem guarantees letters are lowercase alpha).
• The swap-based permutation approach generates permutations in a non-lexicographic order; use visited[] if lexicographic order matters.

---

Cross-Topic Relations

See recursion.md for the general recursive framework that backtracking builds on.
See depth-first-search.md for DFS on explicit graphs.
See dynamic-programming.md for when overlapping subproblems make DP the right alternative.

---

Interview Reference

Must-Know Problems

Subset / Combination problems

• Subsets (78) — baseline subset enumeration
• Subsets II (90) — with duplicates; sort + sibling-skip
• Combination Sum (39) — reusable elements; target pruning
• Combination Sum II (40) — each element once; duplicates in input
• Combinations (77) — fixed size k; forward start index
• Letter Combinations of a Phone Number (17) — multi-branch per level

Permutation problems

• Permutations (46) — classic visited[] template
• Permutations II (47) — duplicates; sort + sibling-skip with visited
• Next Permutation (31) — not backtracking, but tests permutation order understanding

Structure generation

• Generate Parentheses (22) — count-constrained branching; Catalan numbers
• Restore IP Addresses (93) — partition with per-part validity check

Constraint satisfaction

• N-Queens (51) — diagonal set pruning; classic CSP
• N-Queens II (52) — count-only variant
• Sudoku Solver (37) — multiple constraints per cell; hardest common CSP

Partitioning

• Palindrome Partitioning (131) — partition + palindrome check; precompute with DP
• Word Break II (140) — partition with dictionary membership; memoize for efficiency

Grid search

• Word Search (79) — 2D DFS + in-place marking
• Word Search II (212) — multiple words; combine with Trie to avoid redundant DFS

Additional LeetCode Coverage

• Combination Sum III (LC 216)

Clarification Questions to Ask

• "Can elements be reused, or is each element used at most once?" (determines i vs i+1 in recursion)
• "Can the input contain duplicate values?" (determines whether sort + skip is needed)
• "Do you want all solutions or just one?" (affects whether to return immediately after first find)
• "Is there a uniqueness guarantee on the output, or can duplicates appear?" (determines deduplication strategy)
• "For grid problems: can a cell be visited more than once in a path?" (determines marking strategy)
• "What is the definition of a valid partition / assignment?" (clarify the constraint before implementing the goal test)

Common Interview Mistakes

• Appending path instead of path[:] to results — produces a list of references all pointing to the same (now-empty) list.
• Forgetting to remove the last element after recursion — the undo step is missed under time pressure; results grow monotonically instead of backtracking.
• Applying duplicate skip with i > 0 instead of i > start — works for top-level calls but silently drops valid results at deeper recursion levels.
• Checking the goal condition only at the end of exploration — missing early feasibility pruning causes TLE on medium/hard inputs.
• Treating backtracking and DP as interchangeable — backtracking is correct for enumeration; DP is required when only the count or optimal value is needed and states repeat.
• Not sorting the input before duplicate skipping — the skip only works when equal values are adjacent.

Typical Follow-Up Escalations