Recursion & Backtracking
Build a candidate, recurse, undo. The brute force that all DP is an optimisation of.
What you actually need to hold in your head
- Choose, explore, un-choose
- Prune early, that is the whole game
- Draw the recursion tree before coding
- For duplicates, sort then skip equal siblings
Watch it run
Step through the algorithm before you write it.
Place one queen per row. Track attacked columns and both diagonals in sets so every safety check is constant time.
Every element is either in or out. That binary choice at each index builds a decision tree with 2 to the n leaves.
Fix each candidate in the current position by swapping it forward, recurse on the rest, then swap back.
Fill the first empty cell with each legal digit and recurse. Validating as you place, rather than at the end, is what makes it tractable.
Patterns in this topic
The trigger phrases are what you are training yourself to notice.
At each index either take the element or skip it, recursing on the rest and undoing the choice on the way back.
Swap each unused element into the current position, recurse, then swap back.
Place one item per row or cell, validate incrementally, recurse and undo. Pruning is what makes it finish.
Recursion & Backtracking problems
Ordered by sheet phase, so the early ones are the highest signal.