Skip to interview prep
Apexed

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.

How do you decide between backtracking, memoized recursion and dynamic programming — Data structures & algorithms interview question — Apexed