Topic 8 of 20
Think recursively, then explore every choice and undo it: subsets, permutations and search.
Recursion solves a problem by solving smaller copies of the same problem. Every recursive function needs a base case that stops, and a recursive step that makes progress toward it. The fastest way to get comfortable is to trust the function: assume the recursive call correctly solves the smaller problem, and only reason about how to combine its answer.
Backtracking is recursion that explores a tree of choices. At each step you choose an option, recurse, then undo the choice before trying the next one. Almost every subsets, permutations and combinations question fits a single template: choose → explore → un-choose. Duplicates are handled by sorting and skipping equal neighbours at the same depth.
The difference between an accepted and a timed-out backtracking solution is pruning: stop exploring as soon as a partial solution cannot succeed. This topic comes before trees and graphs on purpose, because DFS is just recursion over a structure, and dynamic programming is recursion plus memory.
The standard first recursion; also motivates memoisation later.
A simple base case and reduction, with a bit-trick alternative.
Enumerating combinations of bits; a light warm-up for combinatorial search.
Fast exponentiation by halving; O(log n) recursion.
Solving by relating a node to its parent, not by building the string.
The base template for backtracking and bitmask enumeration.
Sort and skip equal siblings to avoid duplicates.
Swap-based or used-array permutation generation.
Duplicate handling in permutations.
Reuse allowed; a pruned backtracking classic.
Each element used once, with duplicate skipping.
Cartesian-product backtracking; a frequent phone-screen problem.
Generating only valid states instead of filtering them.
Binary choice per character.
Partition a string with a validity check at each cut.
Partitioning with strict segment rules.
DFS on a grid with visited marking and undo.
Shows how sorting and pruning make exponential search feasible.
The canonical constraint-satisfaction problem.
Counting instead of listing; sets or bitmasks for speed.
Full constraint propagation by backtracking.
Carries running totals and handles multiplication precedence.
Minimum removals with deduplication; asked at Meta.