All patterns
Backtracking
Build a candidate step by step and undo when it fails.
time O(2ⁿ) to O(n!)space O(n) stack
What it is
Explore a decision tree: choose, recurse, un-choose. It is exponential by nature, so pruning invalid branches early is what makes it practical.
When to reach for it
- Enumerate subsets, permutations, combinations
- Constraint puzzles (N-Queens, Sudoku)
- Find all valid configurations
Clues in the problem
- “Return all…”
- Small n (roughly ≤ 20)
- Choices that can be checked incrementally
Template
def subsets(a):res, cur = [], []def go(i):if i == len(a):res.append(cur[:])returngo(i + 1) # skipcur.append(a[i]); go(i + 1) # takecur.pop() # undogo(0)return res
Practice problems
- Subsets
- Permutations
- N-Queens
- Combination Sum
- Sudoku Solver
Common mistakes
- Appending the live list instead of a copy
- Forgetting to undo the choice
- No pruning, so it explores hopeless branches