Backtracking: recursion that can undo a choice

Some problems have no formula. You cannot compute the answer directly; you have to try possibilities, and the right one is somewhere in that set. Backtracking handles these problems: build a candidate solution one choice at a time, then undo a choice when it leads to a dead end and try the next one. It is recursion’s most direct descendant and powers the site’s Largest Time and Subset Sum Count problems. Learn the shape first. The code follows.

The shape: choose, explore, undo

Backtracking is depth-first search over a tree of decisions. At each step, make a choice and recurse to see where it leads. Then undo that choice so the next branch starts with the same clean state. That undo matters. It separates backtracking from “copy the partial solution at every step” brute force and gives the technique its name: go down a branch, return to the last decision point when it dead-ends, and try the other option.

The skeleton always uses the same three verbs. The Recursion article explains the machinery underneath:

defp search(state) do
  if complete?(state), do: record(state)     # choose led to an answer
  else
    for choice <- candidates(state) do       # try each next choice
      search(add(state, choice))             # recurse with the choice made
      # the "undo" is implicit: the next loop iteration starts from the
      # original state, because nothing was mutated in place
    end
  end
end

In a pure language, the undo is often free: each recursive call gets its own copy of the state, so “backtracking” means “the next loop iteration uses the unmodified state.” In a language with mutable state, explicitly remove the choice after the recursive call returns. The idea stays the same: extend and unwind one partial solution instead of copying everything at every branch.

The two shapes the site uses

The site’s two backtracking problems sit at opposite ends of the spectrum. Learn both and you can recognize the family.

Permute-and-filter: Largest Time. Given four digits, arrange them into the latest valid "HH:MM" time. The exhaustive approach generates all $4! = 24$ arrangements, keeps only valid times (hour at most 23, minute at most 59), and returns the maximum. The search space is tiny and fixed. Backtracking here means “enumerate every ordering, prune the invalid ones, take the best.” The pruning is the important part: reject an arrangement as soon as its first two digits form an hour over 23, before placing the remaining two digits. Cut the dead branch; do not explore it to the bottom.

Choose-or-not: Subset Sum Count. Given numbers and a target, count how many subsets sum to the target. At each element, the decision tree splits in two: include it or exclude it, then recurse on the rest. The count is the number of leaves that hit the target exactly. This is the recursive half of the Dynamic Programming article’s coin-change shape. Here you are counting completions, not finding a best one, so the overlapping-subproblem cache that dynamic programming adds keeps the exponential count from exploding.

Those two names — “permute and filter” and “choose or not” — cover most backtracking problems you will meet. Permutations, subsets, combinations, and placing problems (queens, sudoku) all fit one of the two shapes; only the candidates and the validity check change.

The skill is the pruning

Pruning makes backtracking fast enough to use: reject a partial candidate as soon as it cannot lead to a valid answer instead of exploring it to the bottom. In Largest Time, the hour must be at most 23, so abandon any arrangement that already exceeds 23 in the first two digits before considering the minutes. In a queens problem, abandon a board with two queens attacking each other before placing more queens. Without pruning, backtracking is exhaustive search, and its cost is the size of the full decision tree — often exponential. With pruning, search the same tree but cut off whole subtrees as soon as they are provably dead. That constant-factor win can make a problem tractable instead of theoretical.

The honest limitation is the one the P vs NP article states: pruning shrinks the tree, but it does not change the fact that the tree is exponential in the worst case. Backtracking is the correct algorithm for exhaustive-search problems: it is as exhaustive as the problem requires, and no smarter. Reach for it when the problem has no shortcut and only a space of possibilities to search.

Where to go next

• Largest Time - the permute-and-filter shape: enumerate, prune, take the best.
• Subset Sum Count - the choose-or-not shape, and the bridge to dynamic programming.
• Recursion - the machinery backtracking runs on: the call stack is the search path.
• Dynamic programming - what you do when the backtracking tree has overlapping subproblems worth remembering.
• P vs NP - the honest ceiling: pruning helps, but some search spaces stay exponential.

Backtracking is recursion with the courage to guess. Build the answer one choice at a time, undo choices that fail, prune branches that cannot work, and the search space — however large — becomes the whole algorithm.