Backtracking:
- Explores all solutions
- Constraint satisfaction (Sudoku, N-Queens)
- Worst case exponential
Dynamic Programming:
- Overlapping subproblems
- Optimization (min cost, max value)
- Polynomial if state space is polynomial
Overlap: Some problems use both. Generate candidates via backtracking, optimize choices via DP.
Rule: If subproblems repeat identically, consider DP. If each state is unique, backtracking may be your only option.