Backtracking vs Dynamic Programming: When to Prune or Memoize

Backtracking and dynamic programming are usually taught in separate chapters, which hides the most useful fact about them: they start from the same place. Both are a recursion over a tree of choices. What differs is what you do about the tree's size — cut branches off, or notice that many branches are the same branch.

Knowing which move applies is most of the work in a hard recursion problem, and there is a single question that decides it.

The problem it solves

Take a list of numbers and a target. Two very different-sounding questions can be asked about it:

• "How many subsets sum to the target?"
• "List every placement of eight queens where none attack each other."

Both are naturally written as a sequence of decisions — take this number or skip it; put this row's queen in column 0, 1, 2… — and both trees are exponential. Written naively, both explore every leaf. But only one of them can be rescued by a cache.

The intuition

Walk down the decision tree and, at any node, ask: what do I need to know to finish from here?

For the subset count, the answer is two numbers: which index you are at, and how much of the target is left. Whether you got to "index 7, 12 left" by taking 5 and 7 or by taking 3, 4 and 5 makes no difference to what happens next. So the huge tree contains the same subtrees over and over, and there are only about n × target distinct ones. Solve each once, store it, and the exponential tree collapses into a table. That is dynamic programming — see what makes a problem DP.

For the queens, the answer is the whole board so far. Which columns are taken, which diagonals are attacked — the entire path matters. Two different partial boards almost never lead to the same future, so a cache would fill with entries that are never hit again. There is nothing to merge. What you can do is refuse to walk into a branch the moment it becomes invalid. That is pruning, and it is backtracking's only real weapon.

Memoization merges branches that are the same. Pruning deletes branches that are hopeless. If the future depends only on a small state, memoize; if it depends on the whole path, prune.

One more signal: if the question asks you to list every solution, the output itself can be exponential, and no cache can make writing it down cheaper. Counting, minimising and "is it possible?" are DP-shaped. Enumerating is backtracking-shaped.

Watch it run

This is the skeleton both techniques share: choose, explore, un-choose, with one path list reused for the whole search. Watch the path grow on every choice and shrink on every un-choose. DP keeps this exact tree and adds a lookup before each descent; backtracking keeps it and adds a validity check.

The code

The same subset count, once as plain backtracking and once with a cache keyed on (i, left). The recursion body is identical; only the decorator differs.

from functools import lru_cache

def count_subsets(nums, target):
    """How many subsets sum to target? Plain backtracking."""
    calls = 0
    def go(i, left):
        nonlocal calls
        calls += 1
        if i == len(nums):
            return 1 if left == 0 else 0
        return go(i + 1, left - nums[i]) + go(i + 1, left)   # take it / skip it
    return go(0, target), calls

def count_subsets_memo(nums, target):
    """Same recursion; the answer depends only on (i, left), so cache it."""
    @lru_cache(maxsize=None)
    def go(i, left):
        if i == len(nums):
            return 1 if left == 0 else 0
        return go(i + 1, left - nums[i]) + go(i + 1, left)
    return go(0, target), go.cache_info().misses

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] * 2
print(count_subsets(nums, 30))        # (6226, 2097151)
print(count_subsets_memo(nums, 30))   # (6226, 1011)

Twenty numbers: over two million calls without the cache, 1,011 distinct states with it. Same answer. The tree was never really two million nodes wide — it was a thousand subproblems, each reached by thousands of different paths.

Now the queens, where there is no small state to cache. The pruning check skips any column already attacked, so hopeless branches die at the row where they fail rather than at the bottom:

def queens(n):
    """Every placement. The state is the whole board, so nothing repeats."""
    cols, d1, d2, out, calls = set(), set(), set(), [], 0
    def place(row, path):
        nonlocal calls
        calls += 1
        if row == n:
            out.append(path[:])
            return
        for c in range(n):
            if c in cols or row - c in d1 or row + c in d2:
                continue                                     # prune: attacked
            cols.add(c); d1.add(row - c); d2.add(row + c); path.append(c)
            place(row + 1, path)
            cols.remove(c); d1.remove(row - c); d2.remove(row + c); path.pop()
    place(0, [])
    return len(out), calls

print(queens(8))                      # (92, 2057)

92 boards in 2,057 calls. Without the check — placing a queen in any column and testing only full boards — the tree has 8⁸, about 16.8 million, leaves.

And the obligatory honesty test: both subset counters against a brute force over every combination, with negative numbers included so that the "left goes negative, stop" shortcut would be wrong.

import random
from itertools import combinations
random.seed(2)
ok = True
for _ in range(500):
    xs = [random.randint(-3, 6) for _ in range(random.randint(0, 10))]
    t = random.randint(-5, 15)
    brute = sum(1 for r in range(len(xs) + 1)
                for c in combinations(range(len(xs)), r)
                if sum(xs[i] for i in c) == t)
    ok &= count_subsets(xs, t)[0] == brute == count_subsets_memo(xs, t)[0]
print(ok)                             # True

The complexity

• Plain backtracking: proportional to the nodes of the decision tree — O(2ⁿ) for take-or-skip, O(n!)-ish for permutations. Pruning lowers the constant, often dramatically, but rarely the worst-case class.
• Memoized recursion: the number of distinct states times the work per state. For the subset count, O(n × range of left) — pseudo-polynomial, since it grows with the target's size, not just n.
• Enumeration: at least the size of the output. Listing every subset is Ω(2ⁿ) no matter what, because that is how many there are.

Where it goes wrong

• Memoizing on the wrong key. If the cached function also reads a mutable path, the cache returns answers computed for a different path. The key must be everything the future depends on — and if that is the whole path, you are in backtracking territory.
• Pruning on a false assumption. "Stop when left goes negative" is only valid when every number is positive. The random test above deliberately includes negatives; that shortcut would fail it.
• Using DP to list solutions. A table can count the ways cheaply, then you still need a backtracking pass to write them out. Problems like word break with "return all sentences" genuinely need both: memoize which suffixes can be split, then enumerate.
• Forgetting to un-choose. A missing path.pop() leaks a choice into every sibling branch — the bug the animation is built around.

How to say it in an interview

"I'll start with the recursion over choices. Then I ask what the future depends on. Here it's only the index and the remaining sum, so the same subproblem is reached by many paths — I'll memoize on (i, remaining), which makes it O(n × target). If the future depended on the whole path, like which columns are used in N-Queens, there'd be nothing to reuse, so I'd prune invalid branches early instead."

Saying why the cache works — the state is small and it repeats — is what turns "I know DP" into an argument an interviewer can follow.