Skip to content
Essay · Craft

What is the difference between backtracking and dynamic programming

The difference between backtracking and dynamic programming is what each remembers: backtracking keeps the whole path, DP keeps only a small state. Here is how to tell which one a problem wants, with a worked example that shrinks 155 million calls to 256 states.

By Vishy10 min readPublished · 17 Nov 2026

The difference between backtracking and dynamic programming is what each one remembers. Backtracking explores every path and undoes choices, so it keeps the whole history. Dynamic programming keeps only a small summary of that history, called the state, and reuses answers for repeated states. If the same state keeps recurring, use DP; if you need the paths themselves, backtrack.

Most explanations stop there, and then you sit in front of a new problem with no idea which side it falls on. This essay is about the decision itself. I will give you a test you can run in under a minute, a worked example with real operation counts, and the cases where the test says no and you should not reach for a memo table at all.

Is backtracking just brute force with pruning?

Mostly yes, and that is not an insult. Backtracking is a depth-first walk through a tree of choices: you pick an option, recurse, and when the recursion returns you undo the pick and try the next one. Pruning means you abandon a branch the moment it cannot lead to a valid answer. The work is proportional to the number of tree nodes you actually visit, and the tree can be exponential.

The defining feature is that the recursion carries the path. When you are three levels deep in an N-Queens search, you hold the exact placement of the first three queens in a mutable structure. That is not an accident of implementation. It is the point, because the validity of the next move depends on those specific earlier moves.

Dynamic programming starts from a different question: does the future of this subproblem depend on the entire path, or only on a few numbers describing where I am? If it is only a few numbers, then two completely different paths that arrive at the same numbers have identical futures. Solving that future twice is waste.

Here is the framing I use, and it is the one idea in this essay that you will not find in a textbook. Think of a travel agent planning a trip. A backtracking agent wants the full itinerary: every city, in order, because the client will read it. A DP agent only wants a ledger with entries like "standing in Lyon, 4 days left, 300 euros left". Two itineraries that end up in the same ledger entry get the same advice for the remaining days. The ledger is the state. The whole skill of dynamic programming is deciding what goes on that ledger line, and the whole skill of backtracking is accepting that sometimes nothing short of the full itinerary will do.

How do you tell whether a problem has repeated states?

Count the distinct states and compare that number to the number of paths. If the states are polynomial and the paths are exponential, the recursion is recomputing the same subproblems and DP will collapse it. If the two counts are about equal, memoization buys you nothing.

Take a concrete case. You have a 16 by 16 grid of cells and want to count the ways to walk from the top-left cell to the bottom-right cell, moving only right or down. Every path has exactly 15 moves right and 15 moves down, so there are C(30,15) = 155,117,520 distinct paths.

The backtracking version is the natural one:

def count_paths(r, c, n):
    if r == n - 1 and c == n - 1:
        return 1
    total = 0
    if r + 1 < n:
        total += count_paths(r + 1, c, n)
    if c + 1 < n:
        total += count_paths(r, c + 1, n)
    return total

This function makes at least one call per path, so well over 155 million calls. At a few tenths of a microsecond per call in Python, that is a minute or more; in a compiled language it is a few seconds. Now increase the grid to 20 by 20 and the path count becomes C(38,19), about 3.5 times 10 to the 10th. That is hours in Python. The code did not change; the input grew by 25 percent in each dimension.

Now ask the ledger question. At cell (r, c), what does the future depend on? Only r and c. The route you took to get there is irrelevant, because the remaining moves are the same regardless. So the state is the pair (r, c), and there are only 16 times 16 = 256 distinct states. Add a cache:

from functools import lru_cache

def count_paths_dp(n):
    @lru_cache(maxsize=None)
    def go(r, c):
        if r == n - 1 and c == n - 1:
            return 1
        total = 0
        if r + 1 < n:
            total += go(r + 1, c)
        if c + 1 < n:
            total += go(r, c + 1)
        return total
    return go(0, 0)

Each of the 256 states is computed once and does two additions, so roughly 512 operations. The ratio against the backtracking version is about 300,000 to 1. The 20 by 20 case needs 400 states. That is the signature of a DP problem: the path count explodes, the state count does not.

Notice that I did not change the recursion. Memoized DP is backtracking with a cache keyed by the state. What changed is a decision: I declared that (r, c) is all the history that matters. If you want the mechanics of the two ways to fill such a cache, memoisation versus tabulation covers it, and the state design template walks through choosing the ledger line.

When is backtracking the only option?

Backtracking is the only option when the answer is the set of paths itself, or when the future depends on so much of the history that no two paths share a state. Generating all permutations, all valid parenthesisations, or all solutions to a Sudoku falls in the first or second group.

Consider listing every permutation of 8 distinct numbers. There are 8! = 40,320 of them, and you must output each one. Any algorithm takes at least 40,320 steps just to write the answer down. A memo table cannot help, because the output size is the lower bound. The same recursion that counts permutations (trivially n!) becomes a backtracking problem the moment the question changes from "how many" to "which ones".

This is the most useful distinction in practice, and it is why the phrase "count the number of ways" and the phrase "return all ways" lead to different algorithms for the same recursion. Subset sum is the clean example. Given 20 numbers and a target, "how many subsets sum to the target" has the state (index, remaining), which is at most 20 times the target range. If the target is 1,000, that is 20,000 states against 2^20 = 1,048,576 subsets. DP wins by a factor of fifty. But "print every subset that sums to the target" must produce each one, so you backtrack, and the cost is proportional to the output plus whatever dead ends pruning fails to cut.

The second group is constraint problems like N-Queens and Sudoku. For N-Queens with n = 12, the future of a partial board depends on which columns and both diagonals are occupied. Two different partial placements almost never produce the same occupied sets, so repeated states are rare and a cache would fill with entries that are never hit. The real gain comes from pruning: placing queens row by row and rejecting attacked squares immediately turns 12^12 raw placements (about 8.9 times 10 to the 12th) into a search of a few hundred thousand nodes. Pruning, not memoization, is the lever.

Can a permutation-like problem still be solved with DP?

Yes, when the order of earlier choices stops mattering and only the set of choices made does. The travelling salesman problem is the textbook case: the number of tours is 20! for 20 cities, about 2.4 times 10 to the 18th, which is out of reach for backtracking.

But the future of a partial tour depends only on which cities have been visited (a subset) and which city you are standing in. That gives 2^20 subsets times 20 current cities, about 21 million states, each with up to 20 transitions: roughly 420 million operations. That is a few seconds in C++ and entirely feasible, versus 10 to the 18th for the path-based search. This is the Held-Karp algorithm, and it is the same trick as the grid: discard the order, keep the summary.

The lesson is that "it looks like permutations" does not tell you which tool to use. What tells you is whether a small summary of the path exists. In the TSP case it does, and it is exponential but far smaller than the path count. In N-Queens it does not, so you prune.

How do the two approaches compare side by side?

They differ in what they store, what they cost, and what they can return. The table below sums up the trade-offs I check when I am deciding.

AspectBacktrackingDynamic programming
What it remembersThe full current path, mutated and undoneA compact state, with a cached answer per state
Cost driverNumber of tree nodes visited (often exponential)Number of states times transitions per state
Grid path count, 16 by 16155,117,520+ calls256 states, about 512 operations
MemoryRecursion depth only, O(depth)One entry per state, can be large
Can list every solution?Yes, naturallyAwkward; reconstruction needs extra work and is limited by output size
Main speed-up toolPruning invalid branches earlyReusing answers for repeated states
Typical problemsN-Queens, Sudoku, permutations, combinations to enumeratePath counting, knapsack, edit distance, coin change, Held-Karp
Fails whenBranching is high and pruning is weakNo small state exists, so the table is as big as the search

Memory deserves its own sentence, because people forget it. Backtracking needs only the stack, so it can run on a problem whose state space would never fit in RAM. A DP table over 2^25 subsets with 8-byte values is 268 MB before you add anything else. Sometimes the right answer is a backtracking search with good pruning precisely because the cache would not fit.

What goes wrong when you pick the wrong one?

The wrong choice fails in one of two recognisable ways: either you time out on an exponential search that had repeated states, or you build a cache that never gets hit and only adds overhead. Both are diagnosable with a small experiment.

For the first failure, add a counter to your recursive function that increments on every call, and a set that records the arguments seen. Run on a small input, say n = 12. If the number of calls is much larger than the size of the set, the same arguments are arriving many times, and memoization will help. In the grid example with n = 12 the calls number C(22,11) = 705,432 while the distinct arguments number 144. That gap is the diagnosis.

For the second failure, run the same experiment and see calls roughly equal to distinct arguments. Then a cache is dead weight. Worse, if you include the path in the cache key (a common beginner mistake, such as passing the list of chosen items as a tuple), every key is unique by construction, and you have turned a backtracking search into a slower backtracking search that also eats memory. If your memo key contains the path, you have not defined a state.

A third mistake is subtler: choosing a state that is too small. If you memoize on (index) alone when the answer also depends on remaining capacity, you get wrong answers that look plausible. The state must contain everything the future reads and nothing it does not. Too much and you lose sharing; too little and you lose correctness.

A decision procedure I actually use

I run through four questions, in order, and they take about a minute.

  1. What is being asked? If the task is to return or print all solutions, plan on backtracking and think about pruning. If it is a count, a minimum, a maximum, or a yes/no, DP is possible.
  2. What does the future read? Write down the variables the remaining recursion looks at. Those are your candidate state.
  3. How many values can the state take? Multiply the ranges. Compare to the number of paths. If the state count is smaller by orders of magnitude, memoize.
  4. Can the state be stored? If the table would be too large, fall back to pruned backtracking, or compress the table (keep only the previous row, for example).

Most of the confusion people describe in why dynamic programming feels so hard sits in step two. Beginners jump straight to filling a table without ever writing down what the future reads. Once that list exists, the table shape follows almost mechanically. It also helps to read the recursion as an inductive claim about its state, which is the habit described in recursion as induction.

Frequently asked questions

Is dynamic programming just backtracking with memoization?

For top-down DP, essentially yes: it is the same recursion with a cache keyed by a well-chosen state. Bottom-up DP drops the recursion and fills a table in dependency order, but it computes the same values. The part that is not mechanical is choosing the state.

Why does backtracking sometimes beat dynamic programming?

Backtracking wins when you must output every solution, when strong pruning cuts the tree to a tiny fraction, or when the state space is too large to store. In N-Queens, partial boards almost never repeat, so a cache has nothing to reuse while pruning cuts the search by many orders of magnitude.

How do I know if my memoization is actually helping?

Count total calls and distinct argument tuples on a small input. If calls greatly exceed distinct tuples, the cache is paying off. If they are about equal, or your cache key includes the path, the cache is only adding overhead.

To practise the state-selection step on a problem where the ledger line is easy to get wrong, work through Coin Change and write down what the future reads before you write any code.