Backtracking is recursion with undo. The goal is not to try everything blindly; the goal is to try only states that can still become valid.
Backtracking Templates
| Template | Use It For | Practice |
|---|---|---|
| Pick or skip | Subsets and subsequences | Subsets |
| Valid state growth | Parentheses and constraints | Generate Parentheses |
| Reuse choice | Combination sum | Combination Sum |
| Grid path | Board search | Word Search |
Backtracking Diagram
choose -> recurse -> undo
stop when valid answer or invalid stateFAQs
What is the difference between recursion and backtracking?
Recursion is the call structure. Backtracking adds choice, constraint checking, and undoing state.
Why do I need to copy the path?
The path list keeps changing. Store a copy when you record an answer.