Section Recap

You've learned complete search: enumerate everything, optionally optimize.

Key techniques:

• Bitmask subsets: $O(2^n)$ enumeration.
• Permutations: $O(n!)$ enumeration.
• Meet in the middle: Reduce $O(2^n)$ to $O(2^{n/2})$.
• Pruning: Cut branches that can't lead to solutions.
• Iterative deepening: BFS optimality with DFS memory.
• Branch and bound: Prune with optimistic bounds.

When to use:

• Small $n$ (check time limits).
• No known efficient algorithm.
• Need guaranteed correctness.

Complete search is the last resort and the first proof of correctness. Learn it and you'll never be stuck.