Meet in the Middle

In short: when a search space is every subset of n items, trying all 2ⁿ is hopeless past about n = 40 — but every subset is exactly one subset of the left half paired with one subset of the right half. Enumerate each half's subset sums on its own (2^(n/2) of them), sort one half, and for each sum in the other half, one binary search finds its best partner. That turns a trillion into about a million: the square root of the search space, traded for memory instead of time.

Left half {7, 13} enumerated to sums 0, 7, 13, 20 and right half {22, 31} to 0, 22, 31, 53: for right sum 31, the best left partner at or under 50−31=19 is 13, giving 44

When Quarry restarts, it warms its cache by preloading index segments from disk, so the first queries don't all miss. The cache has a fixed budget in bytes, and each segment has a size. The warmer wants the set of segments that fills the budget as fully as possible without going over. A fuller cache means fewer cold reads.

python

That's fine for four segments. A real index has about forty, and 2⁴⁰ is roughly a trillion subsets. The knapsack table from the dynamic programming lessons doesn't rescue you either, because it needs one column per byte of budget, and a cache budget is tens of billions of bytes. Backtracking with pruning helps on friendly inputs, but its worst case is still all 2⁴⁰ subsets.

Meet in the middle gets you to about 2²⁰ work, a million instead of a trillion, with an idea that sounds too simple to work.

Split, enumerate, join

Cut the segments into two halves. Every subset of all the segments is exactly one subset of the left half together with one subset of the right half, and its total is the left total plus the right total. So:

Enumerate every subset sum of the left half, and sort them.
Enumerate every subset sum of the right half.
Join: for each right sum r, the best partner is the largest left sum that is at most budget - r. In a sorted list, that's one binary search.

With 40 segments, each half has 2²⁰ ≈ one million sums. Sorting one half and running a million binary searches costs about 2²⁰ × 20 steps, around twenty million, where brute force needed a trillion.

Enumerating a half is easiest by doubling: start from [0], and for each item, keep every sum you have and add a copy with the item included.

step through it

1items = [3, 5, 9]

2sums = [0]

3for x in items:

4 sums = sums + [s + x for s in sums]

5print(sorted(sums))

Here is the same enumeration as a decision tree. Each level decides one item: the left branch skips it and the right branch takes it. The leaves are the half's subset sums, and there are exactly 2³ = 8 of them.

watch it move · tree

One half of the search. Each level doubles the sums, so a half of n/2 items has 2^(n/2) leaves. Both halves together hold far fewer sums than the full tree.

Nothing chosen yet, so the sum is 0. Binary tree, 15 nodes, height 4. At node 0.

1 / 5

The full tree over six items would have 64 leaves. The two half-trees have 8 each.

What does this print?

def subset_sums(items):
    sums = [0]
    for x in items:
        sums = sums + [s + x for s in sums]
    return sums

sizes = [7, 13, 22, 31, 18, 9]
left = subset_sums(sizes[:3])
right = subset_sums(sizes[3:])
print(len(left), len(right), len(left) * len(right))

The join, one binary search at a time

For a right sum r, you want the largest left sum <= budget - r. bisect_right(left, budget - r) returns the position just after the last left sum that fits, so the partner sits one place before it:

What does this print?

from bisect import bisect_right
left = [0, 3, 5, 8, 9, 12, 14, 17]
i = bisect_right(left, 10)
print(i, left[i - 1])

Now watch it. The cells are the sorted left sums. For each right sum, the search narrows lo and hi onto the best partner. Change budget or the items and run it again:

your code, drawn · array

Each right-half sum needs one binary search into the sorted left sums, never a scan. That's what turns 2^n into about 2^(n/2) times n.

Get the bisect wrong and exact fits vanish:

broken — fix it

Segments 20 and 9 fill the budget of 29 exactly, so this should print 29. It prints 28.

Why not just prune harder?

Backtracking, from the algorithm design section, would build subsets one segment at a time and abandon any branch whose total already exceeds the budget. On many inputs that's fast. The trouble is the inputs where it isn't. If most segments are small compared with the budget, almost no branch goes over early, nothing gets pruned, and the search visits nearly all 2ⁿ leaves. Pruning improves the typical case. Meet in the middle improves the worst case, and it doesn't care what the sizes look like.

The two ideas also combine. Each half's enumeration can skip sums that are already over the budget, since no partner could rescue them. That shrinks the lists without changing the method.

❓ Cross-question — "Does it matter where I split?" The time is dominated by the bigger half, so an even split is best: 20 and 20 costs about 2 × 2²⁰, while 10 and 30 costs about 2³⁰, a thousand times more. When n is odd, one half gets the extra item. Sort the smaller half if you can, since it's the one you store and binary search into, and stream the bigger half past it one sum at a time.

The shape of the idea

It helps to name what made this work, because the same shape turns up far from subset sums. The problem had to have three properties:

it splits: every candidate is a pair made of one piece from each half;
the pieces combine simply: the total of a pair is the sum of its parts, so "the best partner for r" is a question about a single number;
that question is searchable: in sorted order (for "closest") or in a hash table (for "exact"), one lookup finds the partner.

Double encryption has the same shape: every key pair is one key from each side, and a match in the middle is an exact lookup. So does searching a huge graph from both ends at once. If a problem has all three, the square root of its search space is within reach.

Coming from Java/JS: Java's Arrays.binarySearch returns a negative insertion point when the key is missing, so decode it with -(result) - 1. In JavaScript there's no built-in bisect, so write the five-line loop from the binary search lesson. Both languages overflow 32-bit integers long before 2⁴⁰, so use long in Java and watch for totals past 2⁵³ in JavaScript.

Counting instead of maximising

Sometimes the question is "how many subsets hit exactly target?". Then the join doesn't need sorting at all. Put the left sums in a Counter, and for each right sum look up how many left sums equal target - r:

python

That's a hash table doing what the sorted list did, in O(1) per lookup instead of O(log). Use sorting when you need "the closest that fits" and hashing when you need "exactly equal".

How much does splitting save?

Brute force does about 2ⁿ work. Meet in the middle does about $2^{n/2} \cdot n/2$ :

n	brute force	meet in the middle	saving
10	1,024	160	6×
20	1,048,576	10,240	102×
28	268,435,456	229,376	1,170×
40	about 1.1 × 10¹²	about 21 million	52,429×

The saving passes a factor of a thousand at n = 28, and it keeps widening, because halving the exponent is worth more than any constant factor. The catch is memory, since a half of 60 items would need a billion stored sums.

Interview problem: the balanced split

Balanced split. Quarry has to split its segments across two storage nodes so the two nodes' totals are as close as possible. Given sizes, return the smallest possible difference between the two totals. Every segment goes to exactly one node, and a node may be empty.

Constraints: 0 ≤ n ≤ 36, 1 ≤ sizes[i] ≤ 10¹². The sizes are far too large for a dynamic programming table over totals.

Examples:

split_evenly([8, 19, 4, 23, 10]) → 2: 8 + 23 = 31 against 19 + 4 + 10 = 33.

split_evenly([]) → 0

If one node gets total s out of T overall, the difference is |T - 2s|, so you want s as close as possible to T / 2. That's the cache warmer's join, except the best partner can be just below or just above the target, so check the neighbours on both sides of the bisect position. That's the boss exercise. The capstone adds a twist: both nodes must get the same number of segments. Then you group each half's sums by how many items they use, and join count c on the left only with count m - c on the right.

What it costs

approach	time	memory
try every subset	O(2ⁿ · n), or O(2ⁿ) with doubling	O(1)
meet in the middle, sorted join	about O(2^(n/2) · n)	O(2^(n/2))
meet in the middle, hashed join (exact target)	about O(2^(n/2))	O(2^(n/2))
DP table over totals	O(n · budget)	O(budget), hopeless for huge sizes

Meet in the middle trades memory for time. It works up to about n = 40 in Python, and past that the stored halves become the problem.

Idioms & real-world patterns

Enumerate by doubling: sums = sums + [s + x for s in sums].
Sort one half, stream the other. You only need to store the half you search into.
Sorted join for "closest", hash join for "exact".
Check both neighbours when "closest" can be on either side of the target, as in the balanced split. bisect only tells you where the target would go.
Where it shows up: attacks on double encryption (encrypt forward from one end, decrypt backward from the other, and meet at a match), bidirectional search in huge graphs, four-list sum problems, and splitting any exponential search whose pieces combine by addition.

⚡ Advanced — a join without binary search

If both halves are sorted, you can join with two pointers instead of a binary search per right sum. Walk the right sums upwards and the left pointer downwards: as r grows, its best partner can only move down. The join becomes linear after sorting.

python

Quick practice

What does this print?

def subset_sums(items):
    sums = [0]
    for x in items:
        sums = sums + [s + x for s in sums]
    return sums

print(subset_sums([2, 5]))

broken — fix it

Three items have 2³ = 8 subsets, so this should print all eight sums. It prints [17] — only the single subset that takes every item — because each step replaces the list instead of growing it.

🎯 Your turn

Build best_warm_set(sizes, budget) for Quarry's cache warmer: the largest total of a set of segments that is at most budget. The empty set counts, so the answer is at least 0.

best_warm_set([7, 13, 22, 31], 50) → 44
best_warm_set([7, 13, 22, 31], 6) → 0

Hint: split sizes in half, sort the left half's subset sums, and for each right sum that fits, bisect_right for its best partner.

Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of the app is built. ✅

Meet in the Middle

Meet in the Middle

Split, enumerate, join

The join, one binary search at a time

Why not just prune harder?

The shape of the idea

Counting instead of maximising

How much does splitting save?

Interview problem: the balanced split

What it costs

Idioms & real-world patterns

⚡ Advanced — a join without binary search

Quick practice

🎯 Your turn

Practice — level up