Backtracking

Many problems ask for every arrangement or selection of some items: all orders in which 4 people can stand in a line, all 3-person teams out of 6 people, all sets of toppings for a pizza. Backtracking lists them by building each answer one piece at a time. It makes a choice, follows that choice as far as it goes, and then takes the choice back so it can try the next one. Every backtracking function repeats the same three moves:

  • Choose: add one item to the partial answer, called the path.
  • Explore: call the function recursively, so the deeper call extends the path further.
  • Un-choose: when that call returns, remove the item again, so the path is exactly as it was before the choice, and move on to the next item.

When the path is a complete answer, it is output and the call returns without choosing anything more (this is the base case). Because every choice is undone on the way back, a single path, used like a stack (push on choose, pop on un-choose), serves the whole search.

The recursion tree

Drawing each call as a node gives the recursion tree. The root is the first call, with the empty path. Each edge is one choice, labelled with the item chosen, and the path at a node is the list of labels on the way from the root down to it. The search visits this tree depth-first: a choose step goes down one edge, an un-choose step comes back up it, and the path on the screen is always the root-to-current-node path. Every complete answer is a leaf, so the answers are output in the left-to-right order of the leaves.

Recursion tree for permutations of A, B, C: the root has edges A, B, C; each node below has one edge per unused item; the six leaves read ABC, ACB, BAC, BCA, CAB, CBA in order #1 to #6; the path root, A, C, B to leaf ACB is highlighted
Every root-to-leaf path is one sequence of choices, so the six leaves are exactly the six orders of A, B, C.

In the animation, nodes on the current path are orange and the current node has a red ring. Nodes whose subtrees are finished turn gray, answer leaves turn green and get their answer number, and each answer is added to the output list below the tree. The Items row shows which items are in the path (orange) or have been passed over (gray), and the Path (stack) row grows on every choose and shrinks on every un-choose.

Permutations

Problem. List every order of n different items, each item used exactly once. For A, B, C there are six: ABC, ACB, BAC, BCA, CAB, CBA.

Idea. Fill the answer one position at a time. The first position can hold any of the n items; the next position can hold any item that is not already in the path; and so on until all n positions are filled. A boolean array used[] records which items are in the path, so the check "not used yet" takes constant time.

permute(path, used):
    if length(path) == n:                      // base case: every item placed
        output(a copy of path)
        return
    for i = 0 to n - 1:                        // try each item in turn
        if not used[i]:
            used[i] = true;  path.push(item[i])     // choose
            permute(path, used)                     // explore
            path.pop();  used[i] = false            // un-choose

start with: path = empty, used = [false, ..., false]

Worked trace, n = 3. This is exactly what the animation shows for A, B, C (indentation = depth in the tree):

root, path = []           choices: A, B, C
  choose A    path = [A]          unused: B, C
    choose B  path = [A B]        unused: C
      choose C  path = [A B C]    complete: output #1 ABC
      un-choose C  path = [A B]   no unused item left here
    un-choose B  path = [A]       next choice: C
    choose C  path = [A C]        unused: B
      choose B  path = [A C B]    complete: output #2 ACB
      un-choose B  path = [A C]
    un-choose C  path = [A]       every choice at [A] tried
  un-choose A  path = []          next choice: B
  choose B ... outputs #3 BAC and #4 BCA, then un-choose B
  choose C ... outputs #5 CAB and #6 CBA, then un-choose C
root: every choice tried, the search ends

Why every permutation appears exactly once. Reading the edge labels from the root to a leaf gives that leaf's answer. The used[] check means a path never contains an item twice, so every leaf is a real permutation. Conversely, any permutation, say CAB, is reached by following the edge C from the root, then A (still unused), then B, because at every node the loop tries all unused items. Two different leaves differ in at least one edge, so they are different orders. Hence the leaves and the permutations match one to one. Since the loop tries items in alphabetical order, the answers come out in dictionary order.

Swapping version. A common alternative keeps the items in an array a and builds the permutation in place. Position start tries each item of a[start..n-1] by swapping it into place, recurses on start + 1, and then swaps it back (the un-choose). It needs no used[] array and has the same tree shape, but its answers are not in dictionary order (for A, B, C: ABC, ACB, BAC, BCA, CBA, CAB).

permuteSwap(a, start):
    if start == n:  output(a copy of a);  return
    for i = start to n - 1:
        swap(a[start], a[i])          // choose a[i] for position start
        permuteSwap(a, start + 1)     // explore
        swap(a[start], a[i])          // un-choose: restore the order

Counting. The root has n children, each of those has n − 1, and so on, so there are n! = n · (n − 1) · … · 1 leaves. Level d has n! / (n − d)! nodes; for n = 4 that is 1 + 4 + 12 + 24 + 24 = 65 nodes. Adding up the levels, the tree has n! · (1/0! + 1/1! + … + 1/n!) < e · n! nodes. Each call's loop looks at all n items and each answer takes n steps to copy, so the running time is O(n · n!). The recursion is n calls deep, so the extra space is O(n) for the path, used[] and the call stack (not counting the output).

Combinations (k of n)

Problem. List every way to pick k of the n items, where order does not matter: {A, C} and {C, A} are the same answer. For k = 2 of A, B, C, D there are six: AB, AC, AD, BC, BD, CD.

Idea. Running the permutation search and stopping at length k would find every set many times (AB and BA). Instead, agree to write each set in increasing order and only build it that way: after choosing item i, the next choice must come after i. Each call receives a start index, the first item it may choose.

combine(path, start):
    if length(path) == k:                      // base case: k items chosen
        output(a copy of path)
        return
    for i = start to n - 1:
        if n - i < k - length(path):           // items i..n-1 are too few
            break                              // prune the rest of the loop
        path.push(item[i])                     // choose
        combine(path, i + 1)                   // explore: later items only
        path.pop()                             // un-choose

start with: combine(empty path, 0)

Worked trace, k = 2 of A, B, C, D.

root, path = []            may choose from A
  choose A   path = [A]    next choices must come after A: B, C, D
    choose B  path = [A B]   complete: output #1 AB,  un-choose B
    choose C  path = [A C]   complete: output #2 AC,  un-choose C
    choose D  path = [A D]   complete: output #3 AD,  un-choose D
  un-choose A  path = []
  choose B   path = [B]    choices after B: C, D
    outputs #4 BC and #5 BD
  un-choose B
  choose C   path = [C]    choices after C: D
    output #6 CD
  un-choose C
  D: n - i = 1 item left (D itself), but k - 0 = 2 are needed: prune D
the search ends
Recursion tree for 2 of A, B, C, D: A has children B, C, D; B has children C, D; C has child D; the root's branch D is dashed and pruned because only one item is left and two are needed; leaves AB, AC, AD, BC, BD, CD
Only allowing later items after each choice builds every set once, in increasing order, and the D branch is pruned because it cannot reach size 2.

Why every combination appears exactly once. Every set of k items can be written in increasing order in exactly one way, and the start index forces every path to be increasing. So each set is built by exactly one path: {A, C} is reached as A then C, and C then A is never tried, because after C only D may follow. Every increasing path is tried, because each loop runs over all items after the last choice.

Pruning. The test n - i < k - length(path) asks whether items i..n-1 are fewer than the items the path still needs. If so, no combination can come from item i or anything later, so the loop stops. This never loses an answer; it only skips subtrees that contain no leaves. The animation draws the skipped choices as faded nodes marked ×. Without the test the search still gives the right answers, but it explores dead ends: for k = n it would visit all 2n increasing paths to output a single answer.

Counting. The number of answers is the binomial coefficient C(n, k) = n! / (k! (n − k)!): the n! / (n − k)! ordered choices of k items, divided by the k! orders of each set. For example C(4, 2) = 6 and C(6, 3) = 20. With pruning, every explored node lies on the path to at least one leaf, so there are at most 1 + k · C(n, k) nodes. Each call's loop costs one step per child plus one for the break, and copying an answer costs k, so the time is O(k · C(n, k)). The recursion is k calls deep: O(k) extra space.

Subsets

Problem. List every subset of the n items, from the empty set ∅ to the whole set (the power set). For A, B, C there are eight.

Idea. A subset is fixed by n yes/no decisions: is A in it? Is B? Level i of the tree decides item i. The left branch includes the item (+A) and the right branch leaves it out (−A).

subsets(path, i):
    if i == n:                            // base case: every item decided
        output(a copy of path)
        return
    path.push(item[i])                    // choose: include item i
    subsets(path, i + 1)                  // explore with it
    path.pop()                            // un-choose
    subsets(path, i + 1)                  // explore without it

start with: subsets(empty path, 0)

Worked trace, A, B, C. Including comes first, so the output order is:

+A +B +C  -> #1 ABC        -A +B +C  -> #5 BC
+A +B -C  -> #2 AB         -A +B -C  -> #6 B
+A -B +C  -> #3 AC         -A -B +C  -> #7 C
+A -B -C  -> #4 A          -A -B -C  -> #8 ∅
Binary tree for subsets of A, B, C: each level decides one item, left edge includes it (+), right edge leaves it out (-); the eight leaves are ABC, AB, AC, A, BC, B, C and the empty set
Three yes/no decisions give a binary tree with 2³ = 8 leaves, one per subset.

For example, after output #1 the search un-chooses C (path = [A B]) and tries −C, which outputs AB. Both branches for C are then done, so it un-chooses B (path = [A]) and tries −B, and so on.

Why every subset appears exactly once. Each leaf is one sequence of n decisions, and each subset has exactly one such sequence (include exactly its own items). So leaves and subsets match one to one.

Counting. Each level doubles the number of nodes, so there are 2n leaves (32 for n = 5) and 1 + 2 + 4 + … + 2n = 2n+1 − 1 nodes (63). Each call does constant work besides copying its answer, which takes up to n steps, so the time is O(n · 2n). The recursion is n calls deep: O(n) extra space. (Summing C(n, k) over all k also gives 2n: every subset has some size.)

How fast it grows

All three searches are as fast as possible for their job, since just writing out the answers takes that long. But the number of answers explodes: 10! = 3,628,800 and 230 is over a billion. That is why this page stops at 4 items for permutations (5 would need 120 leaves side by side), 5 for subsets (32 leaves) and 6 for combinations (at most 30 leaves including the pruned branches). In practice, backtracking is useful when n is small or when pruning cuts away most of the tree.

Common mistakes

  • Forgetting to un-choose. If the item is not popped (or used[i] is not reset), the path keeps growing and later branches start from the wrong state, so answers go missing or come out wrong.
  • Sharing instead of copying the path. There is only one path, and it changes all the time. Storing the path itself in the result list (for example result.append(path) in Python) stores the same list many times, and at the end every entry shows the final, empty path. Store a copy: result.append(path[:]), or new ArrayList<>(path) in Java.
  • Recursing on start + 1 instead of i + 1 in combinations. The next call must start after the item just chosen; otherwise items are repeated and sets appear in more than one order.
  • Duplicates when items repeat. For A, A, B the permutation search prints 6 lines but there are only 3 different orders (AAB, ABA, BAA). Sort the items first, then skip an item equal to the one before it: for permutations, if i > 0 and item[i] == item[i-1] and not used[i-1]: continue; for combinations and subsets (with a loop from start), if i > start and item[i] == item[i-1]: continue. Each different answer is then built once, from its leftmost copies of the repeated items.

Variants

  • Pruning. Any test that proves a subtree has no answers can cut it off before exploring it, like the "too few items left" test above. For search problems with constraints, pruning is what makes backtracking practical.
  • Next permutation (iterative). Permutations can be listed in dictionary order without recursion: find the last position i with a[i] < a[i+1], swap a[i] with the last item larger than it, and reverse everything after position i. Starting from the sorted order and repeating until no such i exists visits each permutation once, and handles repeated items correctly (C++ std::next_permutation).
  • Bitmask subsets. The numbers 0 to 2n − 1 in binary are exactly the include/exclude decisions: bit i of mask says whether item i is in. A plain loop for mask = 0 to 2^n - 1 lists all subsets without recursion (in a different order).
  • Heap's algorithm produces each permutation from the previous one with a single swap, which is useful when the permutation is being tested in place.

Where backtracking is used

The same choose / explore / un-choose pattern, with a validity check before each choice, solves many search problems: the N-Queens problem (place a queen in a row, recurse on the next row, remove it), Sudoku and crossword solvers, graph coloring, finding Hamiltonian paths, subset sum and other puzzles, and generating all test inputs of a small size. When the goal is the best answer rather than all of them, adding bounds on how good a subtree can be gives branch and bound.