82. How do you decide between backtracking, memoized recursion and dynamic programming?
MediumRecursion & backtracking
Technical
Show model answer
Use backtracking when you must enumerate all solutions (all permutations, all N-Queens boards) or when the state is too rich to cache. Use memoization when the recursion revisits the same sub-problem many times and the sub-problem can be described by a few parameters (index, remaining capacity). Caching turns the exponential tree into one call per distinct state.
Bottom-up DP is the same idea with an explicit table and loop order, which avoids stack depth and often allows space optimisation. A quick test: if the answer to a sub-problem depends only on a small key and not on the path taken to reach it, memoize; if it depends on the full path, backtrack.