Combinations and combination sums

A combination is a choice of items in which order does not matter: n items have C(n, k) combinations of size k, and 20 people make 184,756 different teams of 10. Combinations are listed by the backtracking search with a start index, which adds items only after the last one chosen, so each set is built once. Combination sums ask for every choice of numbers that adds up to a target. When a value may be used again, the recursive call keeps the same start index; when each item is used at most once, it moves past it. Sorting lets a loop stop at the first value larger than what is left. A skip rule drops repeated values at one depth.

Two problems about choosing

Problem A: teams with a pair. teams(volunteers, k, pair) lists every team of k volunteers that holds both people of pair or neither. Limits: n ≤ 20. With volunteers A to E, k = 3 and the pair A and B, the teams are ABC, ABD, ABE and CDE.

Problem B: an exact fare. These are combination sums over a purse. fare_combinations(coins, fare) lists every distinct way to pay fare exactly, each coin used at most once, where values repeat. Limits: up to 30 coins, values 1 to 100, a fare up to 500.

• The coins 5, 2, 2, 10, 1, 5, 1 pay 12 in four ways: 1 1 5 5, 1 1 10, 2 5 5 and 2 10.
• When each value may be used any number of times, 2, 5 and 10 pay 12 as 2 2 2 2 2 2, 2 5 5 and 2 10.

The brute force, and where it stops

Try every subset of the positions, keep those whose coins add up to the fare, and drop repeated combinations with a set:

"""Both problems by brute force: every subset of the positions, filtered, repeats dropped with a set."""
import time
from itertools import combinations


def teams_brute(volunteers, k, pair):
    """Every team of k volunteers that holds both of pair or neither."""
    a, b = pair
    return ["".join(t) for t in combinations(volunteers, k) if (a in t) == (b in t)]


def fare_brute(coins, fare):
    """Every distinct combination of coins, each used at most once, that adds up to fare exactly."""
    found = set()
    for mask in range(1 << len(coins)):  # bit i says whether coins[i] is used
        chosen = [coins[i] for i in range(len(coins)) if mask >> i & 1]
        if sum(chosen) == fare:
            found.add(tuple(sorted(chosen)))
    return [list(c) for c in sorted(found)]


print(teams_brute("ABCDE", 3, ("A", "B")))
print(fare_brute([5, 2, 2, 10, 1, 5, 1], 12))

purse = [1, 2, 5, 10, 20] * 6  # 30 coins: six of each value
print("coins  subsets tried  distinct ways to pay 35  time")
for n in (10, 15, 20):
    start = time.perf_counter()
    ways = fare_brute(purse[:n], 35)
    seconds = time.perf_counter() - start
    print(f"{n:5} {1 << n:>14,} {len(ways):>24}  {seconds:.2f} s")
print(f"30 coins: {1 << 30:,} subsets to try")

['ABC', 'ABD', 'ABE', 'CDE']
[[1, 1, 5, 5], [1, 1, 10], [2, 5, 5], [2, 10]]
coins  subsets tried  distinct ways to pay 35  time
   10          1,024                        4  0.00 s
   15         32,768                       12  0.03 s
   20      1,048,576                       20  4.14 s
30 coins: 1,073,741,824 subsets to try

The purse holds six coins each of 1, 2, 5, 10 and 20, and the table uses its first 10, 15 and 20 coins. Every 5 coins more multiply the subsets by 32, so 30 coins cost 1,024 times the work of 20, about half an hour of Python (the constraints lesson gives such budgets), to find a few dozen ways. For teams the brute force is acceptable, C(20, 10) is 184,756, but it still builds teams that break the pair rule before rejecting them.

What to notice

A combination is built once when its values never decrease along a path, and a start index guarantees that. Reuse then means recursing from the same index; using each coin once means recursing from the next one. On sorted coins, the first coin larger than the amount left ends the loop, because every coin after it is at least as large. Two coins of the same value tried at one depth build the same combinations twice.

Choosing k of n, and the bound that stops early Pro: opens with a Pro, Premium or Ultimate pass