Step 3 of 6

Pruning

Exhaustive search gets slow fast, but you rarely need to walk the whole tree. If a partial choice can't possibly lead to an answer, stop exploring that branch. Cutting off hopeless branches early is called pruning, and it's what turns backtracking from a toy into a practical tool.

Choosing k of n

To list every way of choosing k numbers from 1..n (ignoring order), pick them in increasing order: after choosing x, the next number starts from x + 1. That alone avoids listing {2, 1} as well as {1, 2}.

Now prune. If we still need 3 more numbers, starting at n - 1 is hopeless: there are only 2 numbers left. The last useful start is n - need + 1. This program counts how many calls the search makes with and without that bound, for choosing 16 of 20:

#include <iostream>
#include <vector>

long long calls = 0;

void combos(int n, int k, int start, std::vector<int>& cur, bool prune, long long& found) {
    calls++;
    if (static_cast<int>(cur.size()) == k) {
        found++;
        return;
    }
    int need = k - static_cast<int>(cur.size());      // how many more we must pick
    int last = prune ? n - need + 1 : n;               // later starts can't finish
    for (int x = start; x <= last; x++) {
        cur.push_back(x);
        combos(n, k, x + 1, cur, prune, found);
        cur.pop_back();
    }
}

int main() {
    for (bool prune : {false, true}) {
        calls = 0;
        long long found = 0;
        std::vector<int> cur;
        combos(20, 16, 1, cur, prune, found);
        std::cout << (prune ? "with pruning:    " : "without pruning: ") << found << " combinations, " << calls << " calls\n";
    }
}

without pruning: 4845 combinations, 1047225 calls
with pruning:    4845 combinations, 20349 calls

Same answers, 50 times less work. Without the bound, the search wanders into over a million dead ends that run out of numbers before reaching 16.

Pruning on a running total

Pruning is even more powerful when choices have values. Say you must reach a target sum using positive numbers. Sort the candidates first. When the current candidate is already bigger than what's left to reach, every later candidate is bigger still, so the whole rest of the loop can be skipped with break, not just continue.

Reusing a choice

Some problems allow using a choice more than once, like paying an amount with coins. The trick is in the start index: after choosing candidate i, recurse with start i (not i + 1) so it can be picked again, but never go back to earlier candidates. Each combination is then built in non-decreasing order, exactly once.

Your turn: write combination_sum(candidates, target). The candidates are distinct positive numbers, each usable any number of times. Return every combination that adds up to exactly target, each one in non-decreasing order (the list itself can be in any order). Prune with break once a candidate is too big.

Previous: Permutations Next: N-Queens