← Algorithm Design learning pathAlgorithm Design · Module 5 of 10
Backtracking and branch-and-bound
Search solution spaces systematically.
📖 Key ideas
- Backtracking builds solutions step by step and undoes bad choices.
- Examples: N-Queens, Sudoku, subset sum, permutations.
- Pruning skips branches that cannot succeed.
- Branch-and-bound uses bounds to prune optimisation searches.
- Exponential worst case, but pruning helps a lot.
💡 Real-life example: Backtracking is trying routes in a maze and stepping back at every dead end.
BacktrackingTry, check, undo
PruningSkipping hopeless branches
N-QueensPlace N queens without attacks
Branch and boundPruning with cost bounds