Backtracking vs Dynamic Programming
Use backtracking when the question asks for the solutions themselves and you have to enumerate them. Use dynamic programming when it asks for a count or an optimum, because then the identity of each solution does not matter and subproblems can be shared.
Both walk a tree of choices, and they differ in what they do with repetition. Backtracking visits every branch, which is unavoidable when the output is the branches. Dynamic programming notices that different branches arrive at the same subproblem and answers it once, which is only possible when you need an aggregate rather than the paths themselves.
Side by side
| Dimension | Backtracking | Dynamic programming |
|---|---|---|
| Output | Every valid solution, listed | A count, a minimum or a maximum |
| Cost | Exponential, proportional to the answers | States times work per state, usually polynomial |
| Repeated subproblems | Recomputed every time | Computed once, then read from a table |
| Extra space | O(depth) for the recursion | O(states) for the table |
| Pruning | The main lever, cut a branch early | Not applicable, every state is filled |
| Typical n | Small, often 20 or under | Large, thousands or more |
When to pick each
Backtracking
- Generate all subsets, permutations or combinations, where the list is the answer.
- Constraint puzzles such as N-Queens and Sudoku, where a partial board is checked and abandoned.
- Path enumeration, when the question wants every route rather than how many there are.
Dynamic programming
- Counting: how many ways to climb the stairs, how many paths through a grid.
- Optimising: fewest coins, maximum profit, longest subsequence.
- Anything where your recursion keeps asking the same question with the same arguments.
Memoising a backtracking solution that enumerates. A cache can only return an answer that is the same for every caller, and a list of paths through a subproblem is not, because each caller has a different prefix to prepend. Candidates reach for a HashMap, see the count come out wrong, and lose time. The signal that memoisation is available is that the function returns a number, not a collection.
Questions people ask
How do I tell which one a problem wants?
Read what it asks you to return. Give me all the valid boards means backtracking, because the output is the enumeration. Give me the number of valid boards, or the best one by some score, means the identity of each board is irrelevant and states can be shared, which is dynamic programming. The constraint size usually confirms it: n under about 20 invites exponential work.
Is backtracking just DFS?
It is DFS over a tree of choices, with one addition that matters: the undo. The state is shared and mutable rather than copied at every level, which is what keeps it fast, and that is exactly why every change on the way down has to be reversed on the way back up. Forgetting the undo is the defining bug of the technique.
Can one problem use both?
Yes. Palindrome partitioning is the classic pairing: a DP table answers is this substring a palindrome in O(1), and backtracking uses that table to enumerate the partitions. The DP removes the repeated work inside each check while the backtracking produces the list the question asked for.