Trees, graphs and optimization
Backtracking
Explore choices and undo their effects.
Understand the problem
Choose an option, recurse, then restore mutable state before trying another option. Prune a branch only when it cannot lead to a valid answer. Copy completed candidates before storing them.
Make it concrete
N-Queens tracks occupied columns and both diagonals to reject conflicts early.
Trade-offs and pitfalls
Pruning reduces work but does not automatically make an exponential search polynomial.
Check your understanding
Generate subsets and explain the O(n × 2^n) output-size bound.
Practice this topic