Pruning backtracking

Why this matters

A search that tries every option wastes most of its time on options that were already doomed. Suppose you are packing a bag that can hold 10 kilograms, and you have already put in 9 kilograms of books. Every further item you consider makes the bag heavier, so there is no point looking at the rest of the items for this choice. Stopping there is called pruning. The name comes from cutting branches off a tree.

Backtracking is the method from the earlier lessons in this module. You make a choice, explore what follows, undo the choice, and try the next one. The subsets lesson built every subset and checked each one at the end. This lesson checks the answer while the search is running, so that a dead end is abandoned early. The Recursion trees lesson showed the tree of calls. Pruning cuts branches off that tree.

Pruning has a cost of its own. Each check takes a little time. A good prune is a check that is cheap, that never removes a branch holding a valid answer, and that removes a large part of the tree. This lesson shows how to write such checks and how to measure what they save.

The idea: a partial answer that cannot work

A partial answer is the set of choices made so far. In the bag example, the partial answer is the list of books already in the bag. A full answer is a partial answer that has made every choice the problem asks for.

Pruning asks one question at each node of the search tree: can this partial answer still become a valid full answer? If the answer is no, the function returns at once and does not explore the children of that node.

Here is a small case to show the difference. Take the list 1, 2, 3, 4, 5 and look for groups of numbers whose sum is exactly 5. A plain search decides for each number whether to take it or leave it. That gives 2 choices for each of 5 numbers, so 32 groups in total. Each group is built in full and then added up.

The plain search wastes effort. Once a group has a sum above 5, adding more numbers can only make the sum larger, because all the numbers are positive. The search should stop as soon as the sum passes 5.

The next program does that. It sorts nothing, because the list is already in order, and it stops a loop as soon as the next number would take the sum past the target.

C++ · editable

Compile and run it with:

g++ -std=c++20 -Wall -o trace trace.cpp
./trace

The output is:

  pruned: 3 + 3 > 5
  pruned: 4 + 4 > 5
1 4 
  pruned: 1 + 5 > 5
2 3 
  pruned: 2 + 4 > 5
  pruned: 3 + 4 > 5
  pruned: 4 + 5 > 5
5 
calls=10

Read the output in order. The search picks 1 first, then 2. With 1 and 2 chosen the sum is 3, and the next number, 3, would make 6, so the loop stops: pruned: 3 + 3 > 5. Back at the choice of 1, it tries 3 (sum 4). The next number, 4, would make 8, so it stops: pruned: 4 + 4 > 5. Then it tries 4 (sum 5) and prints the group 1 4. The next number, 5, would make 6, so that loop stops too.

The later lines follow the same pattern. The group 2 3 is found, and the group 5 is found from the root. The search made 10 calls in total. It never built the 32 groups.

The break keyword is what does the pruning. It ends the for loop at once. The later numbers were not tried because the list is sorted in increasing order. If the next number is too big, every number after it is also too big.

Worked example 1: the same search, with two stops

The overshoot check uses one fact about the list: it is sorted. The third version adds a second check to the overshoot stop. It uses the total of the numbers still to come.

Call the total of a[i] and everything after it the suffix sum. For the list 2, 3, 5, 7, 8, 10, 12, 15, 20, 25, the suffix sum at position 0 is the total of the whole list, and the suffix sum at the last position is 25. If the partial sum plus the suffix sum is still below the target, then even taking every remaining number cannot reach the target. The branch is dead.

The next program has three versions of the search. The first decides for every number. The second stops on overshoot. The third stops on overshoot and on a short total. It prints how many calls each version made.

C++ · editable

#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

long long calls = 0;

// Version 1: no pruning. Decide for every item, check the sum only at the end.
void plain(const vector<int>& a, size_t i, int sum, int target, vector<int>& cur, int& found) {
    calls++;
    if (i == a.size()) {
        if (sum == target) found++;
        return;
    }
    plain(a, i + 1, sum, target, cur, found);          // leave a[i] out
    cur.push_back(a[i]);
    plain(a, i + 1, sum + a[i], target, cur, found);   // take a[i]
    cur.pop_back();
}

// Version 2: stop a loop when the next item would pass the target.
// The input must be sorted, so every later item is at least as big.
void overshoot(const vector<int>& a, size_t start, int sum, int target, vector<int>& cur, int& found) {
    calls++;
    if (sum == target) { found++; return; }
    for (size_t i = start; i < a.size(); i++) {
        if (sum + a[i] > target) break;
        cur.push_back(a[i]);
        overshoot(a, i + 1, sum + a[i], target, cur, found);
        cur.pop_back();
    }
}

// Version 3: also stop when the rest of the list cannot reach the target.
// suffix[i] is the sum of a[i] and everything after it.
void both(const vector<int>& a, const vector<int>& suffix, size_t start, int sum, int target, vector<int>& cur, int& found) {
    calls++;
    if (sum == target) { found++; return; }
    for (size_t i = start; i < a.size(); i++) {
        if (sum + a[i] > target) break;
        if (sum + suffix[i] < target) break;
        cur.push_back(a[i]);
        both(a, suffix, i + 1, sum + a[i], target, cur, found);
        cur.pop_back();
    }
}

int main(int argc, char** argv) {
    vector<int> a = {2, 3, 5, 7, 8, 10, 12, 15, 20, 25};
    int target = argc > 1 ? atoi(argv[1]) : 25;

vector<int> suffix(a.size() + 1, 0);
    for (int i = (int)a.size() - 1; i >= 0; i--) suffix[i] = suffix[i + 1] + a[i];

vector<int> cur;
    int f1 = 0, f2 = 0, f3 = 0;
    calls = 0; plain(a, 0, 0, target, cur, f1);
    cout << "plain:     calls=" << calls << " solutions=" << f1 << "\n";
    calls = 0; overshoot(a, 0, 0, target, cur, f2);
    cout << "overshoot: calls=" << calls << " solutions=" << f2 << "\n";
    calls = 0; both(a, suffix, 0, 0, target, cur, f3);
    cout << "both:      calls=" << calls << " solutions=" << f3 << "\n";
}

Compile it and run it twice, once with the default target of 25 and once with 90:

g++ -std=c++20 -Wall -o prune_sums prune_sums.cpp
./prune_sums 25
./prune_sums 90

The output is:

plain:     calls=2047 solutions=14
overshoot: calls=95 solutions=14
both:      calls=95 solutions=14
plain:     calls=2047 solutions=7
overshoot: calls=992 solutions=7
both:      calls=172 solutions=7

Three things to notice.

The plain version always makes 2047 calls. With 10 numbers there are 2 choices at each level, and the tree has 2 to the power 11 minus 1 nodes, which is 2047. Pruning never changes this count for the plain version, because it has no checks.

All three versions find the same number of solutions. This check matters. A prune that changes the answer is a bug, not a speed-up. Always compare the answers before you trust the count of calls.

With a target of 25 the suffix check does not help, since the whole list adds up to 107 and the suffix sums are all large. With a target of 90 it cuts the calls from 992 to 172. The suffix check helps most when the target is large compared with the numbers that remain, because then the search would otherwise walk deep into branches that cannot reach the target.

Worked example 2: arrangements with no equal neighbours

Pruning is not limited to sums. The second example is harder because it builds arrangements, which is the permutation shape from the Permutations lesson. The problem: arrange the letters so that no two equal letters are next to each other. For the letters a a b b c c, the arrangement a b a c b c is valid, but a a b b c c is not, because the two a letters touch.

The plain approach builds every arrangement and rejects the bad ones at the end. The pruned approach refuses to place a letter that matches the letter just before it. Once a bad pair is placed, no later letter can undo it, so the branch is dead on the spot.

The program also handles repeated letters. If the letters are sorted and a letter is the same as the one before it, the program uses the later copy only after the earlier copy is already placed. Without this rule the same arrangement would be produced several times.

C++ · editable

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

long long calls = 0;

// Build arrangements one letter at a time.
// prune = false: build every arrangement, then reject the ones with equal neighbours.
// prune = true:  refuse a letter that equals the letter just placed.
void arrange(const string& letters, vector<bool>& used, string& cur, bool prune, long long& found) {
    calls++;
    if (cur.size() == letters.size()) {
        for (size_t i = 1; i < cur.size(); i++)
            if (cur[i] == cur[i - 1]) return;
        found++;
        return;
    }
    for (size_t i = 0; i < letters.size(); i++) {
        if (used[i]) continue;
        // Skip a letter equal to the one before it when that one is unused,
        // so each arrangement is produced only once.
        if (i > 0 && letters[i] == letters[i - 1] && !used[i - 1]) continue;
        if (prune && !cur.empty() && cur.back() == letters[i]) continue;
        used[i] = true;
        cur.push_back(letters[i]);
        arrange(letters, used, cur, prune, found);
        cur.pop_back();
        used[i] = false;
    }
}

int main(int argc, char** argv) {
    string letters = argc > 1 ? argv[1] : "aabbcc";
    sort(letters.begin(), letters.end());
    for (bool prune : {false, true}) {
        vector<bool> used(letters.size(), false);
        string cur;
        long long found = 0;
        calls = 0;
        arrange(letters, used, cur, prune, found);
        cout << (prune ? "pruned:   " : "unpruned: ") << "calls=" << calls << " valid=" << found << "\n";
    }
}

Run it on two inputs:

g++ -std=c++20 -Wall -o arrange arrange.cpp
./arrange aabbcc
./arrange aaaabbbccc

The output is:

unpruned: calls=271 valid=30
pruned:   calls=112 valid=30
unpruned: calls=13299 valid=248
pruned:   calls=1220 valid=248

For a a b b c c there are 30 valid arrangements, and both versions find all 30. The pruned version makes 112 calls instead of 271. For the 10 letters a a a a b b b c c c, the gap is much larger: 1220 calls instead of 13299, which is about 11 times less work, and both find 248 valid arrangements.

The reason the gap grows is simple. The unpruned version keeps building arrangements that already have a bad pair near the start, and it only finds out at the very end. The pruned version drops those branches at the first bad pair, so the number of branches it visits grows much more slowly as the input gets longer.

Writing a prune safely

Before you add a prune, write down three things.

The first is the fact the prune depends on. In the sum search it is "every number is positive, and the list is sorted." In the adjacency search it is "a letter placed in the arrangement never moves." If you cannot name the fact, you are not ready to write the check.

The second is why a pruned branch cannot hold a valid answer. With positive numbers, every extra number adds to the sum, so a sum above the target stays above it. With placed letters, a bad pair of neighbours stays a bad pair, because nothing later can change the letters already in the row. Write this reason as one sentence. If the sentence is false for some input, the prune is wrong for that input.

The third is where the check goes. It must sit in the loop, before the recursive call, so that the call is skipped. A check at the top of the function still costs one call, because the function was already entered. It saves the work inside the call, but the call count stays the same. A check after the recursive call saves nothing, since the work is already done.

Measuring the work pruning removes

A speed-up claim needs two numbers and one check.

The first number is the count of calls, which you get by adding one counter at the top of the recursive function. A call is one visit to a node of the search tree, so the count is a fair measure of work that does not depend on the speed of the machine. The second number is the count of loop checks, which is useful when the prune sits inside a loop. You will see that case in the common mistakes section below.

The check is that every version returns the same answers. Count the solutions, or print them and compare, before you report any number. A prune with a wrong rule can make the count smaller and look like a success.

Timing in seconds is also useful, but it changes from one machine to the next and from one run to the next. Use the call count to compare two versions of the same program, and use a timer only as a second opinion.

Common mistakes

Using `break` on unsorted input

The overshoot version uses break because the list is sorted. If the list is not sorted, break can stop the loop before a valid number is tried. The next program has the same numbers in two orders.

C++ · editable

The output is:

unsorted found=0
sorted found=1

The group 2, 3 has sum 5, so the correct count is 1. With 12 first, the first check 0 + 12 > 5 is true, so break ends the loop before 2 and 3 are tried. The program reports 0 groups, which is wrong. Sort the input first, or use continue instead of break. The next mistake covers continue.

Using `continue` instead of `break`

Replacing break with continue on sorted input does not change the answers. It does change the work, because the loop keeps going and checks every remaining number. The next program counts both the calls and the loop checks for the two choices.

C++ · editable

The output is:

break:    calls=95 checks=174 solutions=14
continue: calls=95 checks=339 solutions=14

Both versions make 95 calls and find 14 solutions. The continue version checks 339 numbers where break checks 174. Nearly half of the loop checks are wasted on numbers that are known to be too big. The prune is still correct, but it saves less work than it could.

Making the bound too strict

The suffix check stops when the partial sum plus the rest of the list is less than the target. A typo that uses <= instead of < removes branches that do hold an exact answer. The sum of the rest of the list can equal the target exactly, and that is still a valid answer.

C++ · editable

The output is:

found=0

The only group is 2, 3, 5, with sum 10. At the first level the suffix sum is 10, which equals the target, so <= stops the search before it starts. The right test is <, which prunes only when the target cannot be reached even by taking everything that is left.

Assuming a fact the input does not have

The overshoot rule is correct only when every number is positive. If the list holds a negative number, a later number can bring the sum back under the target, so stopping at the first overshoot removes valid groups. Write down the fact that your prune depends on, such as "all numbers are positive" or "the list is sorted", and check that the input always has it.

Practice

Exercise 1. Using the overshoot version from the first example, how many groups of numbers from 1, 2, 4 have a sum of exactly 7?

Show the answer

There is 1 group, which is 1, 2, 4, because 1 + 2 + 4 = 7. No other group of these numbers adds to 7.

Exercise 2. How many arrangements of the letters a a b have no two equal letters next to each other?

Show the answer

There is 1 arrangement, a b a. The other two arrangements, a a b and b a a, both contain two a letters next to each other.

Exercise 3. The plain version of the sum search decides for each of 4 numbers whether to take it. How many calls does it make in total, counting the root?

Show the answer

It makes 31 calls. The tree has one root, then 2 nodes at depth 1, 4 at depth 2, 8 at depth 3 and 16 at depth 4. That is 1 + 2 + 4 + 8 + 16 = 31, which is 2 to the power 5 minus 1. In general, n numbers give 2 to the power (n + 1) minus 1 calls.

Exercise 4. Explain in one or two sentences why the suffix check can use break in the loop. Assume the list is sorted.

Show the answer

The suffix sums get smaller as the index grows, because each one drops the first number of the one before. If the check sum + suffix[i] < target is true for some index, it is also true for every later index, so stopping the loop loses no answers.

Exercise 5. How many groups of numbers from the list 1, 3, 4, 8, 9 have a sum of exactly 12? Use a search that prunes on overshoot, then check your count by listing the groups by hand.

Show the answer

There are 3 groups: 3, 9, 4, 8 and 1, 3, 8. Each one adds to 12. A program that checks all 32 subsets prints the same count of 3.

Summary

A pruning check asks whether the partial answer can still become a valid full answer, and returns at once when it cannot.
A break inside the loop stops the search on the rest of a sorted list, which is safe only when the list is sorted in the order the check needs.
A suffix sum gives a second stop that works when the rest of the list is too small to reach the target.
Count the calls for each version, and check that all versions give the same answers before you report a saving.
A missing or wrong bound, such as <= in place of <, removes valid answers and produces a wrong count with no error message.

Pruning backtracking

Why this matters

The idea: a partial answer that cannot work

Worked example 1: the same search, with two stops

Worked example 2: arrangements with no equal neighbours

Writing a prune safely

Measuring the work pruning removes

Common mistakes

Using break on unsorted input

Using continue instead of break

Making the bound too strict

Assuming a fact the input does not have

Practice

Summary

Stuck? Ask the tutor

Using `break` on unsorted input

Using `continue` instead of `break`