Introduction to Backtracking

Some problems have no clever formula. There is no arithmetic that hands you a valid sudoku grid, and no closed form that lists every way to cut a string into palindromes. For those, the only honest approach is to try things.

Trying everything is brute force, and it is usually far too slow. Backtracking is brute force with one addition: the moment a partial attempt is provably hopeless, you abandon it and everything that would have been built on top of it. That single change is the difference between a program that finishes and one that does not.

The term goes back to the 1950s, when D. H. Lehmer coined it. The idea is older than most of the data structures it gets taught alongside.

The state space tree

Every backtracking problem describes a tree, whether or not you ever draw it. The root is the empty attempt. Each edge is one decision. Each node is the partial answer you have built so far.

This tree is never stored anywhere. It exists only as the shape your recursion traces out, which is why it is worth looking at once: the call stack at any moment is exactly one root-to-node path, and returning from a call is exactly a step back up.

One template, every problem

Almost every backtracking solution is the same seven lines. The problem only changes what goes inside them.

function backtrack(state) {
  if (isSolution(state)) {
    record(state);
    return;                     // usually no point going deeper
  }

  for (const choice of choicesFrom(state)) {
    if (!isValid(state, choice)) continue;   // prune: never build this branch

    apply(state, choice);       // choose
    backtrack(state);           // explore
    undo(state, choice);        // un-choose
  }
}

Choose, explore, un-choose. If you remember nothing else from this section, remember those three lines in that order.

Wikipedia's write-up splits this into six named pieces (root, reject, accept, first, next and output), which is the same skeleton with the parts given names. It is worth reading once you have written two or three of these by hand: the Wikipedia article on backtracking.

Watch the tree get built

Generating every subset of a set is the gentlest possible example, because nothing is ever rejected. Every node is a valid answer, so the tree gets built in full and you can watch the shape without any pruning to distract from it.

Follow one branch down to the bottom and then watch what happens on the way back up. The captions alternate between "choose" and "un-choose", and the un-choose frames are the ones people skip when tracing this on paper. They are also where the bug usually is.

Notice there is no separate answer layer. Three items produce eight subsets and the tree has exactly eight nodes. That will not be true of the next problem, and the contrast is the point of starting here.

The un-choose step, and why it bites

The most common backtracking bug is a missing or wrong undo. It rarely crashes. It quietly returns answers that are almost right, which is much worse.

The reason is that the state is shared across the whole search. One array, one board, one string buffer, mutated on the way down and restored on the way up. If a branch forgets to restore something, every branch explored after it starts from a state that never actually existed.

// Broken: the push is never undone, so `current` only ever grows.
function subsetsBroken(items, start = 0, current = [], out = []) {
  out.push([...current]);
  for (let i = start; i < items.length; i++) {
    current.push(items[i]);
    subsetsBroken(items, i + 1, current, out);
    // missing: current.pop()
  }
  return out;
}

// Correct: every choice is undone before the next one is tried.
function subsets(items, start = 0, current = [], out = []) {
  out.push([...current]);          // copy, or every entry aliases the same array
  for (let i = start; i < items.length; i++) {
    current.push(items[i]);        // choose
    subsets(items, i + 1, current, out);   // explore
    current.pop();                 // un-choose
  }
  return out;
}

The other half of that snippet is the copy. Recording current itself rather than a copy of it stores a reference to the one buffer everything shares, so at the end every recorded answer is identical and usually empty.

What it costs

Backtracking is still exponential. Pruning does not change the complexity class, it changes the constant, and the constant is frequently the entire difference between a second and a week.

The worst case rarely happens. That is not a rigorous statement, and it is why backtracking gets described as practical rather than fast: the bound is terrifying, the behaviour on real inputs is usually fine, and there is no general way to predict which you will get.

When to reach for it

Backtracking fits when you need every solution, or when you need one solution and the constraints are tight enough to kill most branches early. It fits badly when you only need the best solution by some measure and the subproblems overlap heavily, because then you are recomputing the same partial answers on many different branches.

The line between backtracking and dynamic programming is blurrier than it looks. Both explore a tree of decisions. Dynamic programming is what you get when you notice the same state keeps recurring and start remembering answers instead of rebuilding them.

Check yourself

Where to read more

Antti Laaksonen's Competitive Programmer's Handbook is a free PDF with a compact chapter on this material, written for people who are about to be timed. It is a good second source precisely because it is terse where this page is chatty.