Backtracking — definition.
Definition
DFS through a decision tree with pruning and state restoration.
Complexity
Exponential in the decision depth; pruning is the whole game.
When to use it
- Generate all subsets / permutations / combinations.
- Constraint-satisfaction (N-queens, sudoku).
- Paths in a grid with branching constraints.
Representative scenarios
- Pizza Topping Combos — subsets of ingredients that meet a rule.
- Radar Placement — N-queens variant on a grid.
- Maze Inscription — word search on a letter grid.
Related patterns
Read the full pattern page: Backtracking — template, code, and drills.
Run the free diagnostic.
Ten-minute patterns quiz. No card. Personalized loop starts on the other side.