Backtracking
Backtracking performs depth-first search over a decision tree. It makes a choice, updates state, explores, and restores the exact previous state before trying the next choice.
def search(state):
if is_solution(state):
record(state.copy())
return
for choice in candidates(state):
if not feasible(state, choice):
continue
apply(state, choice)
search(state)
undo(state, choice)
Design checklist
- Define what one search-tree level means.
- Decide whether choices are positions, values, edges, or assignments.
- Make the solution condition and output ownership explicit.
- Pair every mutation with an exact undo, including early-return paths.
- Add only pruning rules proven unable to remove a valid required solution.
Pruning types
- Feasibility: a constraint is already violated.
- Symmetry: equivalent choices would generate duplicate states.
- Bounds: even the best possible completion cannot improve the incumbent.
- Memoization: the same residual state has already been solved; this begins to overlap with dynamic programming.
Complexity
Worst-case time is often exponential or factorial because output or search-space size is itself that large. Pruning improves explored instances, not necessarily the worst-case class. Stack depth is usually proportional to the number of decisions, excluding stored outputs.
Use backtracking when a witness or complete enumeration is required and the constraints can reject partial assignments early.
Termination and what counts as complete
A finite input does not by itself guarantee termination: a recursive call must decrease a well-founded measure, such as the number of unassigned positions. Searching a graph instead of a decision tree may require a path-local visited set to prevent cycles. A global visited set can wrongly suppress different required witnesses that reach the same vertex with different histories.
The template above stops at a solution, so it assumes solutions are leaves or that extensions need not be reported. With positive subset-sum values, reaching the target allows an immediate return; with zeros, extending a solution can produce further valid witnesses. Likewise, a shallow copy() suffices for a list of immutable integers but not for nested mutable state.
For two binary choices, the decision paths are 00,01,10,11: append 0, recurse through both second choices, pop 0, then repeat with 1. After each return the path must equal its exact entry value. Exhaustiveness follows because each valid solution has a sequence of choices, and sound pruning removes none of those required sequences. A small exhaustive baseline is useful for checking a proposed pruning rule.
Two concrete decision trees
Permutations explains choosing an unused element, restoring state and avoiding duplicate outputs. Subset sum branches on inclusion or exclusion and shows why zeros or negative values change valid pruning. The underlying traversal is depth-first search, but each backtracking path carries its own decisions, not merely a visited vertex.