JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Meet in the Middle

When pruning has run out of room, you can sometimes attack the exponent itself: split the decisions into two halves, brute-force each half alone, and let the two halves shake hands in the middle. The payoff is turning roughly 2^n work into about 2^(n/2) — the difference between hopeless and doable.

When clever pruning is not enough

The last three guides all played the same game: keep brute force's honesty but refuse to look at candidates that cannot matter. Backtracking cut off subtrees that already broke a rule, and branch and bound cut off subtrees whose best possible outcome could not beat the answer in hand. But pruning has a ceiling. On a hard instance with few constraints to exploit, the search space can stay stubbornly close to 2^n no matter how sharp your bound is — there simply are not enough doomed branches to cut. When that happens, shaving the tree is not the move. You need to attack the exponent itself.

Here is the trick in one sentence, and it is genuinely different from everything before: meet in the middle splits the n decisions into two halves of n/2 each, brute-forces each half completely and separately, then combines the two lists of partial results. Each half has only 2^(n/2) candidates instead of 2^n, so you do two cheap sweeps and pay a modest cost to join them — rather than one ruinous sweep over everything. The whole gain comes from the fact that 2^(n/2) + 2^(n/2) is laughably smaller than 2^n: at n = 40 that is roughly a million plus a million, versus a trillion.

A worked example: subset-sum, halved

Take the cleanest case, the one we met under subset-sum: given n numbers and a target T, is there a subset that adds up to exactly T? Plain brute force tries all 2^n subsets (enumerating subsets by counting bitmasks). Now split the numbers into a left half L and a right half R, each of size n/2. Any subset of the whole is a left part plus a right part, and its sum is (sum of the left part) + (sum of the right part). That additivity is the hinge: the two halves do not interfere, so we can deal with them one at a time.

  1. Enumerate all 2^(n/2) subsets of the left half L and store their sums in a list A. Likewise enumerate all 2^(n/2) subsets of the right half R into a list B.
  2. Sort B (or load it into a hash set). This is the one preparation step that lets the matching go fast.
  3. For each sum a in A, ask: does B contain the value T - a? If a left part contributes a, we need the right part to contribute exactly the rest. A hit means a + (T - a) = T — a real subset of the whole reaching the target.
  4. Looking up T - a costs O(log(2^(n/2))) = O(n) with sorted B and binary search, or O(1) on average with a hash set. Run this lookup for all 2^(n/2) values of a and you have your answer.

Notice the role of the sort: it turns the second half from a list we must scan into a structure we can probe. Asking "is T - a present?" by binary search is exactly the trick that makes the join cheap, and it is no accident that meet-in-the-middle leans on a sorted half — searching a sorted set is the natural partner of generating an unsorted one.

Counting the cost — and why it works

Let m = 2^(n/2) be the size of each half's list. Generating A and B costs O(m) each. Sorting B costs O(m log m), which is linearithmic in m. The matching does m lookups at O(log m) each, another O(m log m). Add it up and the whole method is O(m log m) = O(2^(n/2) * n) time. Compare that to the O(2^n) of plain brute force: the exponent has been cut in half. That is the entire prize, written in one line.

plain brute force:   O(2^n)
meet in the middle:  O(2^(n/2) * log(2^(n/2)))
                   = O(2^(n/2) * n)

n = 40:  2^40  ~ 1.1e12   vs   2^20 * 40 ~ 4.2e7
         (about a trillion)     (about 40 million)
The same problem, two cost models. Halving the exponent is the headline; the extra factor of n from sorting and searching is the small print.

Why is it correct? The same complete-enumeration promise we have leaned on all rung, just split in two. Every full subset is some left part paired with some right part, and step 1 generates every left part and every right part, so every pairing is reachable. Step 3 checks, for each left part, whether the exact right part it needs exists. Nothing is missed, because the additive split is exhaustive on both sides; nothing is double-counted in a way that fools a yes/no question. The combine step is doing the work that the missing half of the brute-force sweep used to do — it just does it by lookup instead of by re-enumeration.

What it costs you — and where it stops

Nothing this good is free, and the bill is paid in memory. Plain brute force can run in O(1) extra space — generate one candidate, test it, throw it away. Meet in the middle must store a whole half's worth of partial results to look them up later: O(2^(n/2)) space. That is a real trade, and it is the classic time-for-space bargain. For n = 40 the lists hold about a million entries each, which is comfortable; for n = 60 they hold about a billion, which is the new wall. Meet in the middle moves the cliff, roughly doubling the n you can handle — but the cliff is still exponential, now in n/2.

There is also a precondition that is easy to forget: the two halves must combine through some clean, searchable relation. Subset-sum works because partial sums add and "need T - a" is a single exact lookup. The 0/1 knapsack version works similarly, though you must keep only the non-dominated (weight, value) pairs in each half before matching. But if the halves interact in a tangled way — every left choice changing what every right choice means — there is no tidy join to exploit, and the method does not apply. Meet in the middle is a specialist's tool: superb when the decisions split additively, useless when they do not.

Where it sits, and where to go next

Step back and see the shape of this whole rung. We opened with honest, blind generate-and-test, then learned to make the generator smart: prune infeasible branches, bound away hopeless ones. Meet in the middle is the odd cousin — it does not prune at all. Instead it borrows a move from a different family entirely, the split-and-combine idea you will study head-on in the divide-and-conquer rung. The difference is that classic divide-and-conquer recurses on both halves and merges; here we brute-force each half flat and merge once. Same instinct (a problem split in two is more than twice as easy), different gear.

That last pointer is the bridge out of this rung. Everything here has been about taming exhaustive search — making "try everything" survivable by enumerating in order, pruning the doomed, bounding the hopeless, and, today, splitting the exponent. The next rungs change strategy entirely: instead of cleverly searching all candidates, they avoid building most of them, by reusing the answers to overlapping subproblems. Carry one lesson forward above all: the search space is the thing to size first, because its size is what decides whether you may enumerate at all — and what kind of cleverness you must summon if you may not.