Algorithms · advanced
Backtracking
Backtracking incrementally builds candidate solutions, abandons a partial candidate as soon as it cannot lead to a valid solution, and undoes the latest choice before trying another.
Why it matters
It provides a clear, correct framework for combinatorial search and gains practical speed when constraints prune large subtrees early.
Mental model
How to reason about backtracking
Each recursion level owns one decision. Choose, update state, test feasibility, explore, then restore exactly the state that choice changed before considering its sibling.
Analogy
Solving a maze with chalk: mark a chosen corridor, turn back immediately at a dead end, erase that mark, and try the next corridor from the last junction.
Examples
See the boundary, not just the happy path
Worked example · N-Queens pruning
place a queen only if its column and diagonals are unusedA conflicting partial board cannot become valid by adding more queens, so its entire subtree is discarded.
Worked example · Restore mutable state
path.add(choice); search(); path.removeLast()Undoing after recursion makes every sibling branch start from the same parent state.
Avoid · Forget the undo step
used.add(choice); search(next) // choice remains usedState leaks from one branch into its siblings, silently removing valid candidates and producing incomplete results.
Common mistakes
Misconceptions to remove early
Pruning without a proof
A pruning rule must show no completion of the partial state can work. A heuristic suspicion can delete valid solutions.
Copying all state by default
Copies may make correctness simple but can dominate runtime. Prefer disciplined choose-and-undo when mutation is localized and restoration is reliable.
Quick check
Can you predict the result?
1. What must happen after returning from a branch that mutated shared search state?
- • Restore the state to exactly what it was before that branch's choice
- • Keep every mutation for the next sibling
- • Restart the entire program
2. When is a backtracking prune correct?
Keep building