Backtracking: Choose, Explore, Unchoose

Backtracking is a way to list every solution to a problem, or find one, by building it one choice at a time: make a choice, search everything that can follow it, then undo the choice and try the next. This card covers those three steps, the tree of partial solutions they walk, and the problems that call for them.

Suppose a shop sells three add-ons, numbered 1, 2 and 3, and you want every bundle a customer could buy, from none of them to all three. Nested loops would do for three add-ons, but not for a number of add-ons that is only known at run time, and the problems below will not fit loops at all. Backtracking handles any number with one function.

It keeps one list, the path, holding the choices it has made: a partial solution. For each add-on in turn it makes two choices, take it or skip it. To take add-on 1, it appends 1 to the path (choose), searches every bundle that starts that way (explore), and removes the 1 again (unchoose). Then it searches every bundle without add-on 1. When every add-on has been decided, the path is a complete bundle, and the search records a copy of it.

The choices form a state-space tree: each node is a partial solution, each branch is one choice, and each leaf is a complete one. A run of the search on the three add-ons printed the tree below, with each leaf's note giving the bundle recorded.

The tree has 15 nodes and 8 leaves, one per subset, recorded in the order {1, 2, 3}, {1, 2}, {1, 3}, {1}, {2, 3}, {2}, {3}, { }. The search never holds more than one path: it walks down a branch, records the leaf, steps back up by undoing the last choice, and walks down the next branch. That stepping back is the backtrack the method is named after.

In general, backtracking explores a tree of partial solutions depth first with one shared path. At every node it asks whether the path is complete, and if so records a copy; otherwise it tries each choice still available, searching from each and undoing it afterwards. Because every choice is undone, each branch starts from exactly the path its parent had.

A maze walker who always takes the next untried turning and walks back to the last junction at a dead end is searching the same way, one route held at a time. The likeness breaks on the goal: the walker wants one exit and stops there, while a backtracking search that lists everything visits every dead end on purpose.

It is not backtracking to build every subset by copying the whole list at every call and never undoing anything. That gives the same answers, but each call pays for a copy of the path, where backtracking copies only at the leaves it records.

Reach for backtracking when a problem says list every, find all, or find any arrangement that satisfies some rules: subsets, orderings, seatings, puzzle placements. Its cost grows with the size of the tree, which for subsets of n items is 2ⁿ leaves, so it suits small n or trees that rules can cut short.

Choose, explore, unchoose is the whole method; everything else in the topic is about where to record, how big the tree is, and how to cut it down.