When branches overlap
Plain backtracking re-solves identical subproblems whenever different decision paths reach the same state. Memoized backtracking stores the result for each distinct state the first time it is computed, then returns the cached value on later visits. This fuses the flexibility of recursion with the efficiency of dynamic programming.
What makes it work
- The recursion must depend only on a compact state, not the full path taken to reach it.
- That state, perhaps an index plus a remaining target or a bitmask of used items, becomes the cache key.
- The answer for a state must be a deterministic function of that state, so caching is sound.
When these hold, the number of distinct states, not the number of root-to-leaf paths, bounds the work. An exponential search can collapse to polynomial.
Where it fits and where it does not
Memoization shines for counting or optimization questions, like how many ways or the best value, where many paths share subproblems. It does not help when you must list every distinct solution, because each full solution is unique and cannot be folded into a single cached value.
Key idea
When recursion depends only on a compact state, caching each state collapses overlapping subproblems, turning exponential backtracking into efficient dynamic programming for counting and optimization.