Backtracking
Backtracking = choose, explore, and undo across many problem shapes, not just subsets.
The idea
Backtracking is a disciplined recursive search over a decision tree. At each frame you mutate a candidate (choose), recurse (explore), then restore mutable state (undo) before trying the next option.
Subsets is one instance, but the same control flow powers permutations, combination sum, N-Queens, palindrome partitioning, and word search with pruning.
Like trying keys on a ring: insert one key, test the lock, remove it, and try the next until a full sequence works.
When to reach for it
- Need all valid configurations or paths.
- Constraints can prune branches early.
- The next choice depends on mutable partial state.
Language-independent template
search(state):
if complete: record
for choice in choices(state):
if prune(choice): continue
choose(choice)
search(next_state)
undo(choice)Complexity — time Exponential in branching depth, space O(depth) recursion + mutable candidate.
Common mistakes
- Forgetting to undo mutable state before the next branch.
- Recording references instead of snapshot copies.
- Missing prune checks and exploding the tree.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Enumerate valid times using exactly a chosen number of lit LEDs.
Return the power set of distinct input values.
Place n queens so no two attack each other.