skip to content

Why does splitting a 40-item exhaustive subset search into two halves of 20 reduce the work from about 2^40 to about 2^20?

level: seniorimportance: nice to knowfreq 28%

answer

  1. attack the exponent, not the constant
  2. two halves, one join
  3. square root of the work
  4. a key the other half matches
  5. memory becomes the binding limit

basics

~20 s

Each half has only 2^20 subsets, so both are enumerated cheaply. One half is stored in a structure keyed by its partial contribution, and each subset of the other half is matched against it. The exponent halves; storing 2^20 entries is the price.

solid answer

~40 s

Enumerating every subset of 40 items is about 1.1 x 10^12 combinations. Split the items into two halves of 20 and neither half is large: each has 2^20, roughly 1.05 million, subsets. Enumerate the left half, store each subset under a **key** summarising its contribution, and sort or index that store. Then enumerate the right half and, for each subset, look up the key that would complete it — the partner it needs to hit the target or to minimise the combined cost. Cost becomes `O(2^(n/2) * n)` time and `O(2^(n/2))` space instead of `O(2^n)`: about 4 x 10^7 operations against 10^12, roughly four orders of magnitude. The precondition is that a half's effect collapses to a key the other half can match against.

code

pseudocode · 18 lines
pseudocode
left  = items[0 .. 19]          # 2^20 subsets
right = items[20 .. 39]         # 2^20 subsets

store = empty list
for each subset s of left:
    append(store, total(s))
sort(store)

best = none
for each subset t of right:
    need = target - total(t)
    partner = nearest_at_or_below(store, need)
    if partner exists:
        combined = partner + total(t)
        if best is none or combined closer to target than best:
            best = combined

report best

go deeper

for a junior

Recall that splitting an exhaustive subset search into two halves and matching them up is far cheaper than walking every combination, because each half is exponentially smaller than the whole.

for a middle

Explain the arithmetic and the join: 2^n becomes two lots of 2^(n/2), one side is stored under a key and the other queries it, and memory now grows exponentially too.

for a senior

Show judgment about when to reach for it: the instance just past exhaustive reach, an objective that decomposes into summarisable halves, and a memory budget that can hold the stored side.

for a principal

Recognise that it buys roughly a doubling of exact reach and no more. Decide whether that headroom is worth the specialised implementation or whether the growth curve calls for a different approach now.

## The starting point An overnight run must choose a subset of 40 candidate jobs hitting a target load exactly, or as close as possible. Enumerating every subset means 2^40 = 1,099,511,627,776 combinations — about 1.1 x 10^12. At any plausible per-combination cost that does not finish by morning. **Meet in the middle** attacks the exponent rather than the constant. ## Why halving the exponent is so violent Split the 40 items into a left half and a right half of 20 each. Every complete subset of the original 40 is exactly one left subset combined with one right subset, so nothing is lost. But each half has only 2^20 = 1,048,576 subsets — about a million. - Enumerating **both** halves is 2 x 2^20, roughly 2.1 x 10^6 subsets built. - Sorting one half's keys costs about 2^20 x 20, roughly 2.1 x 10^7 comparisons. - Looking up each right-half subset costs another ~20 steps, another 2.1 x 10^7. Total is around 4 x 10^7 operations against 1.1 x 10^12 — a factor near 2.7 x 10^4, about four orders of magnitude. The general shape is `O(2^(n/2) * n)` time and `O(2^(n/2))` memory, replacing `O(2^n)`. Since 2^(n/2) is the square root of 2^n, the technique is sometimes described as square-rooting the work. ## The join is the whole trick The halves must be recombined, and that is only possible when a half's effect on the objective **collapses to a key** the other half can look up: - For a target sum, the key is the half's total, and a right subset with total `t` needs a left subset with total `target - t`. - For a cost being minimised, store each left key with the best cost achieving it, and query for the partner that completes the objective most cheaply. - For coverage-style objectives the key can be a set of covered elements, though the key space then grows and the memory advantage can evaporate. When the halves genuinely interact — when the value of a right-half choice depends on *which* left subset was taken and not merely on a summary of it — there is no key, and no join. ## What you pay | | Plain enumeration | Meet in the middle | |---|---|---| | Time | `O(2^n)` | `O(2^(n/2) * n)` | | Memory | `O(n)` | `O(2^(n/2))` | | Precondition | none | halves must join on a key | | Fails when | n is beyond about 30-40 | memory for 2^(n/2) runs out | Memory is the real cost and the real limit. At n = 40 the store holds about a million entries: comfortable. At n = 60 it holds 2^30, over a billion: no longer comfortable. At n = 80 it is 2^40 and hopeless. **The technique moves the wall, it does not remove it** — roughly doubling the n you can handle exactly, until memory becomes the binding constraint instead of time. ## Practical notes 1. Split for **balance**, not convenience. Cost is dominated by the larger half, so 20/20 beats 25/15: 2^25 is 32 times 2^20. 2. Store the half whose keys **compress** better. If many left subsets share a total, keeping only the best entry per key shrinks the store substantially. 3. The stored half should be the one you query against, so choose the sorted side to make the lookup a single search rather than a scan. 4. This is an **exact** method. Both halves are fully enumerated and every combination is accounted for by the join, so the answer is optimal — unlike a heuristic, which returns something good with no such claim. ## Where it sits among the options Meet in the middle is worth reaching for when the instance sits *just* beyond exhaustive reach and you still need an exact, defensible answer: the structure is simple, the implementation is short, and the result is provable. It does not help when the objective refuses to decompose into two summarisable halves, and it is the wrong tool when n is far past the wall, where the honest options are a pruned exact search run against a deadline or a heuristic reported as such. Knowing which of those three situations you are in is most of the value of knowing the technique.

  • Why split the items into two equal halves rather than, say, 25 and 15?
    Cost is dominated by the larger half. A 25/15 split enumerates 2^25 subsets on one side, 32 times the 2^20 of a balanced split, while the smaller side saves far less in absolute terms. Balance minimises the maximum, which is what the runtime and the memory both track.
  • Does meet in the middle make the problem tractable?
    No. The cost is still exponential, just with the exponent halved, and the memory for 2^(n/2) entries becomes the binding constraint first. It roughly doubles the instance size you can solve exactly and then hits a wall of its own. It is a better constant-in-the-exponent, not a change of complexity class.

saying these in an interview costs you the question

  • Claiming the split makes the search polynomial
  • Ignoring that the store holds 2^(n/2) entries in memory
  • Splitting unevenly because one side is easier to enumerate
  • Applying it where a half's effect cannot be summarised as a key
  • Calling the result approximate when both halves are fully enumerated