When to use

Use backtracking for constraint satisfaction and combinatorial generation: permutations, combinations, subsets, N-queens, sudoku, valid arrangements.

Rules

Pattern: make a choice, recurse, undo the choice (backtrack)
Prune early — skip branches that already violate constraints to avoid exploring dead ends
For subsets: at each element, choose to include or exclude it (2^n total)
For permutations: choose each unused element at each position (n! total)
ALWAYS pass state by reference and undo mutations rather than copying
NEVER copy state — it's wasteful and slow
If the problem says "generate all" or "find all valid," backtracking is usually the right approach

Subsets: 2^n. Permutations: n!.