Backtracking: the search tree, undoing state, pruning dead branches

← Back to the section

Dynamic programming answers "how many ways" and "what is the maximum". Sometimes, though, you need not a number but the variants themselves: every set of vouchers adding up to the required sum, every arrangement, every route. That is the job of backtracking — an organised walk over the tree of variants that drops hopeless branches in time.

The tree of variants

Any exhaustive search can be drawn as a tree: the root is the empty solution, one element is added at every level, and the leaves are finished variants.

Let us collect every set of denominations that adds up to exactly the required sum. At each step we decide which denomination to add next; the remainder shrinks; reaching zero means the set is ready, going below zero means a dead end.

Walking such a tree is naturally written with recursion: a call is a step down a level, a return is a step back up.

The three mandatory parts

Every backtracking search is made of the same three pieces. A stopping condition — the current set is already an answer (or already hopeless). A loop over the choices of this step — what may be added right now. And the undo: after the recursive call returns, the current state is restored so that the next choice at the same level can be tried. That retreat is what gave the technique its name.

live example

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class Combinations {
    public static void main(String[] args) {
        int[] nominals = {5, 2, 3};
        Arrays.sort(nominals);
        List<List<Integer>> result = new ArrayList<>();
        walk(nominals, 0, 8, new ArrayDeque<>(), result);
        System.out.println(result);
    }

    static void walk(int[] nominals, int from, int rest, Deque<Integer> current, List<List<Integer>> result) {
        if (rest == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = from; i < nominals.length; i++) {
            if (nominals[i] > rest) break;
            current.addLast(nominals[i]);
            walk(nominals, i, rest - nominals[i], current, result);
            current.removeLast();
        }
    }
}

The pair current.addLast(...) and current.removeLast() is that undo. Forgetting the second line is the most common mistake here: the set keeps collecting leftovers from neighbouring branches and the answers drift.

The second subtlety is new ArrayList<>(current) when an answer is stored. Storing current itself is not allowed: it is a mutable object, by the end of the search it is empty, and the result turns out to be a list of empty lists.

Pruning is the whole point

Without pruning the search grows explosively and is hopeless on any input of noticeable size. A pruning check is one that lets you skip a branch which provably holds no answers. There are two of them in the example.

By value. The line if (nominals[i] > rest) break; cuts the loop short: the data is sorted, so once the current denomination already exceeds the remainder, every later one exceeds it too. That is exactly why the array is sorted up front.

By order. The recursion receives i, not i + 1 and not zero. Zero would allow going back to earlier denominations, and the sets {2,3} and {3,2} would count as different. Passing i allows repeating the same denomination but forbids moving backwards — so every set is born exactly once.

The classic example: queens

Place eight queens on a board so that none attacks another: a full run over all arrangements is around four billion of them. Backtracking places queens one per row and, before descending, checks whether the new queen collides with those already placed. A branch where a conflict has appeared ends immediately — and four billion turn into a few thousand checks.

How few exactly is visible if the nodes are counted inside the program.

live example

public class Queens {
    static int solutions;
    static int nodes;

    public static void main(String[] args) {
        place(new int[8], 0);
        System.out.println("solutions: " + solutions);
        System.out.println("tree nodes: " + nodes);
    }

    static void place(int[] column, int row) {
        nodes++;
        if (row == column.length) {
            solutions++;
            return;
        }
        for (int c = 0; c < column.length; c++) {
            if (safe(column, row, c)) {
                column[row] = c;
                place(column, row + 1);
            }
        }
    }

    static boolean safe(int[] column, int row, int c) {
        for (int r = 0; r < row; r++) {
            if (column[r] == c || Math.abs(column[r] - c) == row - r) return false;
        }
        return true;
    }
}

The program prints 92 arrangements and 2057 tree nodes: the safe check before every descent shrank billions of variants down to two thousand steps. The earlier a dead end is recognised, the more of the tree is cut away.

How it differs from dynamic programming

The two techniques are neighbours, and the choice goes like this. You need the variants themselves — only a search will do: a list of answers cannot physically be "folded into a number". You need a count or the best variant and the subproblems overlap — then dynamic programming wins: it never builds the variants, it folds them into a number, and it is far faster for that.

Sometimes the two are combined: a search with a notebook of what has already been computed. But when there are as many states as there are variants, there is nothing to remember — an honest search is all that is left.

How to recognise the technique

• The task asks to list all sets, arrangements, routes or partitions.
• The answer is a list of lists, not a number.
• The input is small (dozens of elements): a search is expensive by nature and large inputs are beyond it.
• There is a rule by which part of the variants can be dismissed in advance.

How this is done in Java

The search itself is not in the standard library — it is a technique, not a structure. All of its state, though, is held by ready-made collections, and the choice of class shows up directly in speed: a search repeats the same operations millions of times, and an extra O(n) inside one step gets multiplied by the whole tree.

The current set in the example above is an ArrayDeque: inside it is a circular array, addLast and removeLast cost amortised O(1), and both halves of the undo touch the same end of that array, that is, the hot cache. LinkedList can do the same, but it allocates a node object for every element added — in a search that means pressure on the garbage collector and extra cache misses.

Answers are collected in an ArrayList, and the copy new ArrayList<>(current) costs O(k) — a separate array for every set. Hence the conclusion: memory is eaten not by the depth of the recursion but by the number of stored answers; with millions of answers the task runs out of memory before it runs out of time. The sorting the denominations are put through is a plain Arrays.sort over primitives, O(N·log N) once before the descent.

The trap is in the check "this element is already taken". It is tempting to ask current.contains(x) of the set itself, but contains on a list and on an ArrayDeque is a linear O(n) scan on every step of the tree, quietly multiplying the whole complexity by the length of the set. For that check people take a boolean[] used when the elements are numbered, or a HashSet for anything else — both answer in O(1). And ArrayDeque does not accept null — that is a NullPointerException, so an "empty move" has to be spelled out with an explicit placeholder.

In short

• Backtracking is a walk over the tree of variants by recursion, undoing the state after every branch.
• Three mandatory parts: the stopping condition, the loop over the choices of a step, the undo of the changes.
• A forgotten undo and storing a mutable object instead of a copy are the two most common mistakes.
• Pruning decides everything: eight queens are four billion arrangements by brute force and 2057 nodes with a check before each descent.
• Passing the current index instead of zero stops the same set from appearing in a different order.
• Need the variants themselves — a search; need a count or a maximum — dynamic programming.

What to read next

• Recursion — the descent and return the whole technique rests on.
• Dynamic programming — the neighbouring technique for when you need a number, not the variants.
• Stacks and queues — ArrayDeque, the handy place to keep the current set.
• Graphs — depth-first search: the same descent with a return, only along edges.