Combinations and pruning

A combination is a choice of k items in which the order doesn't matter: from 1, 2, 3 and 4 you can choose two numbers in 6 ways, and choosing 2 and 1 is the same as choosing 1 and 2. To build each combination only once, pick the numbers in increasing order: after choosing x, the next number starts from x + 1.

def combos(n, k, start, path):
    if len(path) == k:
        print(path)
        return
    for x in range(start, n + 1):
        path.append(x)
        combos(n, k, x + 1, path)
        path.pop()


combos(4, 2, 1, [])

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

itertools.combinations(range(1, 5), 2) gives the same six, as tuples and in the same order, and math.comb(n, k) counts them without making them: n! / (k! (n - k)!).

Pruning: stop where a branch can't work

Often a branch is hopeless long before it reaches the bottom of the tree. Say you're choosing 5 numbers from 1 to 9, you have chosen 2 so far, and the loop is about to try 8 as the third. After 8 only 9 is left, a single number, but the combination would still need two more: whatever the call for 8 does, it can't finish. Not making that call at all is called pruning: one check cuts a whole subtree off the tree. With need numbers still to pick (this one included), the numbers from x to n must hold at least need of them, so x can go up to n - need + 1 and no further. This program counts the calls the search makes with and without that bound, choosing 12 numbers from 1 to 15:

calls = 0


def combos(n, k, start, path, prune):
    global calls
    calls += 1
    if len(path) == k:
        return 1
    need = k - len(path)
    last = n - need + 1 if prune else n
    found = 0
    for x in range(start, last + 1):
        path.append(x)
        found += combos(n, k, x + 1, path, prune)
        path.pop()
    return found


for prune in [False, True]:
    calls = 0
    found = combos(15, 12, 1, [], prune)
    print("prune:", prune, found, "combinations,", calls, "calls")

prune: False 455 combinations, 32647 calls
prune: True 455 combinations, 1820 calls

Both searches find all 455 combinations, but the pruned one makes 18 times fewer calls. The other spends almost all its time in branches that run out of numbers before they hold 12.

Pruning on a running total

Numbers that add up give even better chances to prune. Say you have a gift card worth 10 and a list of prices, and you want to know how many sets of items cost exactly 10. Each call picks one more price, always from further right in the list than the last one it picked (another way to build every subset exactly once), and passes down what's still left on the card. If the prices are sorted, the first price that doesn't fit tells you that none of the later ones fit either, so break leaves the whole loop at once. (continue would give the same count, but it would go on trying prices that are bigger still.)

calls = 0


def ways(prices, start, remaining):
    global calls
    calls += 1
    if remaining == 0:
        return 1
    total = 0
    for i in range(start, len(prices)):
        if prices[i] > remaining:
            break                   # sorted: the rest are bigger still
        total += ways(prices, i + 1, remaining - prices[i])
    return total


prices = sorted([9, 3, 7, 1, 8, 2, 6, 4, 5, 10, 12, 11])
print(ways(prices, 0, 10), "ways,", calls, "calls")

10 ways, 43 calls

The take-or-leave search of the first step makes 8,191 calls for 12 prices, whatever the target.

Forgetting to sort

The break is only right because the prices are sorted. Run the same search on the prices in the order they came:

def ways(prices, start, remaining):
    if remaining == 0:
        return 1
    total = 0
    for i in range(start, len(prices)):
        if prices[i] > remaining:
            break
        total += ways(prices, i + 1, remaining - prices[i])
    return total


prices = [9, 3, 7, 1, 8, 2, 6, 4, 5, 10, 12, 11]
print(ways(prices, 0, 10), "ways without sorting")
print(ways(sorted(prices), 0, 10), "ways after sorting")

5 ways without sorting
10 ways after sorting

Half the ways are gone, with no error. After taking 9, only 1 is left on the card, and the next price, 3, is too big: break ends the loop before it reaches the 1 further along, so 9 + 1 is never counted. In an unsorted list, a price that doesn't fit says nothing about the prices after it. When a pruned search finds too few answers, check that the order the break relies on is really there.

What pruning buys

Pruning doesn't change the worst case: when nothing can be cut (many small numbers and a big target), the search is still exponential. But it often turns an impossible search into an instant one. For the numbers 1 to 40 and a target of 30, take-or-leave walks through all 2⁴⁰ subsets, about a trillion, while the pruned search finds the 296 ways in 2,035 calls. Sorting costs O(n log n), nothing next to the search, and it is what lets break cut the rest of the loop. The recursion goes only as deep as the numbers in one subset, so it stays shallow.