Backtracking template
Why it exists
Problem: Generating all combinations, permutations, or configurations of a set by brute force uses too much memory if we copy the state for every possibility.
Naive approach: Generate all possible states blindly, often by allocating new memory for every single node in the state-space tree, then filter out the invalid ones.
Better idea: Use a single shared mutable state. Make a choice, recurse to explore that choice, and then 'un-choose' (undo) the change when the recursion returns. This keeps memory usage strictly bounded to the depth of the recursion tree.
Mental model
Like exploring a maze with a single piece of string: you walk down a path, and if it's a dead end, you rewind your string back to the fork and try the next path.
Backtracking is simply depth-first search on a dynamically generated state-space tree. The state is shared across all recursive frames. When moving down the tree (recursing), we apply a choice. When moving up (returning), we undo that choice. This guarantees that each branch explores from a clean state.
Repeated decision: What are all the valid choices from the current state? For each, choose it, explore it, and un-choose it.
Explanation
Backtracking is not a new algorithm; it is plain recursion where each stack frame makes a choice, recurses, and then explicitly undoes that choice so the shared state remains clean for the next option. The 'undo' step is the entire trick.
The skeleton looks like this in Python:
```python
def backtrack(state):
if goal(state):
record(state.copy())
return
for choice in options(state):
apply(choice)
backtrack(state)
undo(choice)
```
Each `backtrack` call is a stack frame. The state-space tree is exactly the recursion tree. The un-choose step happens on the way UP the tree, which is just 'work during unwinding'.
Complexity-wise, backtracking does not change the worst-case exponential bounds (e.g., O(2^n) or O(n!)). However, pruning (stopping early when a path is invalid) changes the PRACTICAL size of the searched tree, transforming intractable problems into solvable ones.
Key points
- State sharing: The state is identical before and after exploring a branch. That is what 'un-choose' guarantees.
- Pruning: By halting recursion early when a state becomes invalid, backtracking avoids exploring massive dead subtrees.
Pattern: Backtracking Template
Recognition cues:
- Phrases like 'generate all', 'all combinations', 'all permutations', 'all ways'
- Phrases like 'exists a path/assignment'
- Input constraints are very small (n <= 20)
When not to use
- Counting-only questions: If you only need to count the number of ways (not list them), Dynamic Programming can count without enumerating, saving exponential time.
- Optimization with overlapping subproblems: If the same sub-states are reached multiple times, standard backtracking wastes time. Use DP (memoization) instead.
- Finding a single feasible answer in a monotone space: Use binary search on the answer instead of combinatorial search.
Common mistakes
- Appending a reference instead of a copy: The most common bug is `results.append(state)` instead of `results.append(state.copy())`. Because the state is shared and mutable, if you append a reference, every recorded answer will eventually mutate to the final state (usually empty) when the recursion unwinds.
- Forgetting to un-choose: If you forget to undo the choice after the recursive call returns, sibling branches will inherit a polluted state from previously explored paths.
Recall questions
- What is the primary difference between standard recursion and backtracking?
- Why must you record a deep copy of the state when a solution is found?
- How does backtracking save memory compared to a naive generate-all approach?
Questions & answers
A student's backtracking code returns a list of empty arrays: `[[], [], []]`. What is the bug?
They appended a reference to the shared state array instead of a deep copy. When the recursion fully unwound, the shared state became empty, mutating all references in the results list.
Approach: Recognize the classic mutable reference trap in Python/JS backtracking.
Given a grid, find all valid paths from start to end without revisiting cells.
Use backtracking. Mark a cell as visited, recurse to neighbors, and unmark it when returning.
Approach: Identify the 'all paths' keyword and small grid size as a backtracking cue.
Continue learning
Previous: Recursion tree
Previous: The call stack
Next: Subsets
Next: Permutations
Next: Combination sum
Next: N-Queens