Costing a Backtracking Search by Counting Its Leaves

The cost of a backtracking search that lists every solution is the number of leaves in its tree times the work done at each leaf, which is usually the copy of the solution. This card shows how to count the leaves for subsets and permutations and why the copy belongs in the cost.

A team generates every ordering of the stops on a delivery route to pick the shortest. With 6 stops it is instant; with 12 it never finishes. Counting the leaves before writing the search says which it will be.

For subsets, each of the n items is taken or skipped, two choices per level and n levels, so the tree has 2ⁿ leaves. For permutations, the first position has n choices, the second n − 1, and so on down to 1, so the tree has n × (n − 1) × … × 1 = n! leaves. At each leaf the search copies the path into the result, which takes one step per item, so it does n steps per leaf. A run counted leaves and copied items for n from 1 to 6.

So listing every subset costs O(n · 2ⁿ) and listing every permutation O(n · n!). The inner nodes add no more than a constant factor: in a tree whose every inner node has at least two children, there are fewer inner nodes than leaves. A common slip is to quote O(2ⁿ) or O(n!) by counting only the leaves; that leaves out the copy, which is n times larger. For 4 items that is the difference between 24 permutations and the 96 items copied.

In general, cost a backtracking search as leaves × work per leaf, plus the inner nodes when they do real work. Count the leaves from the choices per level: multiply the number of choices at each level together.

No cleverness can beat this when the task is to list everything, because the output itself has n · n! items for permutations and the search must write each of them. Pruning helps only when most leaves are not solutions, which is the case for puzzles and constrained arrangements rather than for plain listings. The route team's 12 stops have 12! = 479,001,600 orderings; at 13 the count passes six billion, which is why such searches either prune hard or give way to dynamic programming, a later topic.

Count the leaves before you write the search: the count says whether it can finish.