Backtracking vs. Dynamic Programming: How to Choose

Backtracking explores choices and undoes them to try alternatives. Dynamic programming reuses the answer when multiple choice paths reach the same subproblem. They can work together: a recursive search can become a memoized dynamic program when its repeated states have a precise meaning.

To choose an approach, ask what the output must contain and whether different histories can share the same remaining work.

Start with a small subset problem

Given [1, 2, 3, 4], list the subsets whose values sum to 7. Use each position at most once.

At each position, choose whether to include its value. One path includes 1 and 2, skips 3, then includes 4. Another skips 1 and 2, then includes 3 and 4.

The answers are [1, 2, 4] and [3, 4].

Backtracking follows these branches while keeping the current selection. After exploring a branch that includes a value, remove that value from the current selection before trying the branch that excludes it.

That undo step restores the state for the next choice. Forgetting it makes later branches inherit decisions that do not belong to them.

Find the repeated subproblem

Now change the question to: does any subset sum to 7?

Consider the moment after the first three positions have been considered. One branch has selected 1 and 2. Another has selected only 3. Both have total 3, both have only the final 4 left to consider, and both need another 4.

For a yes/no answer, their remaining task is identical. Define a state as:

canMake(i, remaining)

Its meaning is: can some subset of positions from i onward produce the remaining sum?

Both branches reach canMake(3, 4). Compute its answer once and reuse it. The earlier selections differ, but the answer to this remaining feasibility question does not.

This is the same habit of precise state definition used in our dynamic programming guide.

What belongs in a memoization key?

The remaining sum alone is not enough. With [1, 2, 3, 4], making a remaining sum of 3 is possible while the 3 is still available. It is impossible when only the 4 remains.

The index tells you which choices are still legal. Omitting it combines different problems and can produce a wrong answer.

Other problems need different information. A path through a grid may depend on which cells have already been used. A capacity problem may need both an item index and remaining capacity. A state must capture everything that affects future choices or the answer being requested.

If you cannot explain why two histories have interchangeable futures, don't merge them into one cached state yet.

Listing, counting, and existence are different outputs

In the subset example, [1, 2] and [3] can share a feasibility answer for the remaining 4. But when listing results, both earlier selections still need their own completed answer.

Caching a count or a Boolean does not print those distinct subsets for you. You can combine dynamic programming with reconstruction, but the work needed to produce the requested output still matters.

Also define whether equal values at different positions count as different choices. This article's example uses distinct values, so that ambiguity does not arise.

Pruning and memoization save different work

Pruning stops a branch once you know it cannot lead to a valid answer. For positive values and a fixed target, a partial sum above the target cannot recover by adding more values.

That rule fails if negative values remain. With target 3, choosing 5 can still work if a later -2 is available. The condition that makes a pruning rule safe belongs in its explanation.

Memoization instead prevents solving an identical remaining problem more than once. A state can be valid and still benefit from caching because many paths reach it.

Compare the costs under clear assumptions

For n distinct values, include-or-exclude search has up to 2^n leaf choices. Materializing all subsets takes O(n × 2^n) total time in the worst case because writing the results also costs work. A depth-first search uses O(n) working space for its path and recursion, apart from stored output.

For nonnegative integer values and integer target T, subset-sum feasibility can use O(nT) dynamic programming states, each with constant work under fixed-cost arithmetic. This is called a pseudopolynomial bound: it depends on the numeric target, which can be much larger than its encoded length.

Dynamic programming is therefore not automatically the smaller computation. Compare the reachable state space with the search you would otherwise perform.

Ask the output question first

Before choosing a technique, complete two sentences: “The answer must contain…” and “Two branches have the same remaining problem when…”

Those answers tell you whether to enumerate paths, reuse states, or do both. Use Hourly DSA for short approach-selection practice, and the steps for getting unstuck when the state still feels too vague to define.

Read next

Once you recognize repeated subproblems, define exactly what one stored answer should mean.

Dynamic Programming: Start by Defining the State →