Stage 1 · Code
Graphs & Backtracking
Backtracking Template
The choose-explore-unchoose framework for exhaustive search with pruning — systematically explore every candidate and backtrack when the path is invalid.
The Pattern
Backtracking is a brute-force search over all possibilities, modeled as a decision tree. At each node you make a choice, recurse, then undo the choice (backtrack). The pattern is always: choose an option, explore recursively, unchoose.
The difference between backtracking and naive recursion is the key insight: you prune branches that cannot lead to a valid solution before recursing deeper. This turns O(2ⁿ) into something tractable for constrained inputs.
Always validate the partial solution before recursing. A well-placed constraint check at the top of the recursive function can eliminate entire subtrees of exploration.
The Template
When to Use
- Generate all permutations, subsets, or combinations of a set.
- Constraint satisfaction (N-Queens, Sudoku solver, crossword).
- Combinatorial optimization where exploring all possibilities is feasible.
- n ≤ 20–30 — backtracking is exponential; beyond that you need pruning or DP.
- Path finding in a maze with obstacles — explore every route.
Problems
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.