Searching a tree of decisions
Backtracking solves problems framed as a sequence of choices, such as placing queens, filling a sudoku, or generating valid parentheses. It walks a tree of partial solutions depth first, and crucially it undoes a choice once that branch is exhausted so the same structures can be reused.
The choose explore unchoose rhythm
Every backtracking routine follows one shape.
- Choose a candidate and add it to the current partial solution.
- Explore deeper by recursing on the smaller remaining problem.
- Unchoose by removing that candidate, restoring the state for the next option.
A base case detects a complete solution and records it. The undo step is what separates backtracking from naive recursion: it lets one mutable working set serve the entire search instead of copying state at every node.
Pruning dead branches
The real power comes from pruning. Before exploring a choice, a constraint check can reject it immediately, cutting away an entire subtree. Strong pruning is the difference between an elegant search and an explosion of dead ends.
Key idea
Backtracking chooses a candidate, recurses, then unchooses to restore state, while constraint checks prune whole subtrees that cannot lead to a solution.