Meet in the middle algorithm for n up to 40

The meet in the middle algorithm solves a search over every subset of n items by splitting the items into two halves, searching each half on its own, and combining the two lists of results. For n = 40 that replaces 2⁴⁰, about 10¹², subsets with two lists of 2²⁰, about a million totals each, which a laptop handles in seconds. The classic case is choosing items whose total comes as close as possible to a target.

The problem: gifts closest to a voucher

1. Prices 9, 14, 21, 35 and 52, voucher 60: the answer is 1. No set totals 60, and 9 + 52 = 61.
2. Prices 400, 250, 175, 990, 610, 330 and 85, voucher 1000: 10, from 990 alone or from 400 + 610.
3. Prices 12, 7 and 30, voucher 5: 2, from the 7 alone, which beats the empty set’s 5.

The brute force, and why it fails at these sizes

Compute the total of every subset, each from the subset that lacks its lowest item, and keep the closest:

# The brute force: the total of every subset, each built from the subset one smaller, and the closest one kept.
import time


def closest_brute(prices, voucher):
    totals = [0] * (1 << len(prices))  # totals[mask]: the total of the items whose bits are set in mask
    best = abs(voucher)
    for mask in range(1, len(totals)):
        low = mask & -mask  # the lowest item of the subset
        totals[mask] = totals[mask ^ low] + prices[low.bit_length() - 1]
        best = min(best, abs(totals[mask] - voucher))
    return best


print(closest_brute([9, 14, 21, 35, 52], 60))
print(closest_brute([400, 250, 175, 990, 610, 330, 85], 1000))
print(closest_brute([12, 7, 30], 5))

print(" n        subsets   time")
prices = [100_000_000 + (i * 7_919_003) % 900_000_000 for i in range(40)]
for n in range(14, 21, 2):
    start = time.perf_counter()
    closest_brute(prices[:n], sum(prices[:n]) // 3)
    seconds = time.perf_counter() - start
    print(f"{n:2}  {2 ** n:13,}  {seconds:5.2f} s")
print(f"40 items: 2 ** 40 = {2 ** 40:,} subsets, about {seconds * 2 ** 20 / 86400:.0f} days at that speed")

1
10
2
 n        subsets   time
14         16,384   0.00 s
16         65,536   0.01 s
18        262,144   0.05 s
20      1,048,576   0.71 s
40 items: 2 ** 40 = 1,099,511,627,776 subsets, about 9 days at that speed

The three answers are right. Each extra item doubles the work, so 20 items, a million subsets, already take a noticeable fraction of a second in Python, and 40 items mean 1,099,511,627,776 subsets, days even at that speed. A compiled language at roughly 10⁸ simple steps a second still needs hours. Pruning cannot rescue it either: with a target to approach from both sides, no partial total is hopeless.

What to notice

• Every subset is two subsets. Its items in the first half form one subset and its items in the second half another, so its total is a total of the first half plus a total of the second.
• Half of 40 is small. Each half of 20 items has only 2²⁰ = 1,048,576 subsets.
• For one left total the best partner is fixed: the right total nearest to V minus that left total.

Four techniques follow:

• Splitting into halves lists every subset total of each half, about 2 × 2^(n/2) totals instead of 2ⁿ.
• Sorting one half lets a binary search find, for each left total, the nearest right total.
• Two pointers sweep both sorted halves once, from opposite ends, and pass every pair that could be closest.
• Merging by doubling builds a half’s totals already sorted, so no separate sort is needed.

Splitting the items into two halves, step by step Pro: opens with a Pro, Premium or Ultimate pass