Continue here
Backtracking vs DP — comparison
Both explore a state space. Backtracking enumerates (or searches) decisions; DP remembers overlapping subproblems for an optimal/count answer. Pick with the table, then open the deep dive.
| You need… | Prefer | Guide |
|---|---|---|
| All subsets / perms / constructions | Backtracking | Backtracking |
| One optimal value with overlapping subs | DP | Dynamic programming |
| Existence under constraints (sudoku) | BT + prune | Backtracking |
| Count ways with overlapping structure | DP (or memoized BT) | Dynamic programming |
How to study this pair
- Start with backtracking — subsets then perms.
- Add one prune-heavy problem (N-Queens or Word Search).
- Move to DP — state sentence before code.
- One 1D (robber/coins) + one 2D (paths/LCS).
- Contrast: Combination Sum (BT) vs Coin Change (DP) — same flavor, different ask.
Interview takeaway
Don’t grind both as one blob. Enumerate vs remember — different talk tracks.
Shared practice set
- Subsets / Permutations
- Combination Sum
- Generate Parentheses
- House Robber
- Coin Change
- Unique Paths / LCS
Pattern bank (hub links)
Eight high-yield questions across this hub — open the deep dive for full solutions.
- Subsets — choose/skip
- Combination Sum — reuse with prune
- Permutations — swap or used[]
- N-Queens / Word Search — place + undo
- Coin Change — unbounded knapsack
- LIS — DP O(n²) or patience O(n log n)
- Edit Distance — 2D DP
- Unique Paths / Robber — rolling DP