Meet in the middle

41 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

From the numbers 5, −7, 3, 5, choose any of them (possibly none) so that their sum is as close as possible to 6. By hand you list the subsets and their sums: the full list has 2⁴ = 16 entries, and you find that 3 + 5 − 7 + 5 = 6 hits the goal exactly. With 40 numbers, 2⁴⁰ subsets is about a trillion, too many to list. Dynamic programming over sums does not help either when the numbers can be huge, because the table of possible sums becomes enormous.

The trick is to notice that a trillion is a million squared, and a million is affordable.

Build the structure, one piece at a time

Piece one: split the array into two halves, left [5, −7] and right [3, 5]. Every subset of the whole array is some subset of the left half joined with some subset of the right half.

Piece two: list the subset sums of each half separately. With 2 numbers per half that is 4 sums each:

Piece three: sort the right-hand sums: 0, 3, 5, 8. Now for each left sum a, the right sum we would like is 6 − a, and the closest available one is found by binary search in the sorted list, checking the neighbour on each side of the insertion point:

1. Left 0 wants 6: nearest right sums are 5 and 8; 0 + 5 = 5, distance 1.
2. Left 5 wants 1: nearest are 0 and 3; 5 + 0 = 5, distance 1.
3. Left −7 wants 13: nearest is 8; −7 + 8 = 1, distance 5.
4. Left −2 wants 8: exactly 8 exists; −2 + 8 = 6, distance 0.

The best distance is 0, so a subset sums exactly to 6. Listing the subset sums of a half can itself be done by the mask loop from the subset-enumeration pattern, or by doubling: start with [0], and for each number append a copy of every existing sum plus that number.

Why it is correct

The invariant is that every subset of the whole array corresponds to exactly one pair (left subset, right subset), and its sum is the left sum plus the right sum. So the closest subset sum to the goal is the closest value of a + b over all pairs, with a from the left list and b from the right. For a fixed a, |a + b − goal| is smallest when b is nearest to goal − a, and in a sorted list the nearest value to a target is one of the two values around the insertion point, which the binary search finds. Taking the minimum over all a therefore gives the true optimum.

Why it is fast

Each half has n/2 numbers and so 2^n/2 subset sums. Listing them costs that much per half; sorting the right list costs 2^n/2 · (n/2); and each of the 2^n/2 left sums does one binary search of about n/2 steps:

time = O(2^n/2 · n), against 2ⁿ for the full listing

For n = 40 that is roughly a million times 40, about 40 million steps, against a trillion. The exponent halved, which is why the method is called meeting in the middle. Memory is the two lists, O(2^n/2).

How to recognise it in an interview

Cues: n around 30 to 40, "choose a subset", sums or products that are too large for a DP table, "closest to", "minimise the difference", or four arrays to be combined where two at a time is manageable. Say: "2ⁿ is too many but 2^n/2 is fine, so I will enumerate each half and match the halves with a sorted list or a hash map".

Closest Subsequence Sum is the walk-through. 4Sum II has four arrays: count the sums a + b from the first two in a hash map, then for each c + d from the last two look up −(c + d), turning n⁴ into n². Partition Array Into Two Arrays to Minimize Sum Difference adds a size constraint, so the lists are kept per subset size and the matching is done size by size.

02The idea in one line

Split into two halves, enumerate each, match complements with a sorted list or set.

Reach for it when: Partition to minimise sum difference, closest subsequence sum, 4Sum II.

Cost: O(2^(n/2) · n) time.

03The walk-through, step by step

The video works one example: Closest Subsequence Sum on [5,-7,3,5] goal 6. These are its captions in order, so you can follow without the video or check a step you missed.

1. 2^n subsets is too many; 2·2^(n/2) is fine. Split the array
2. Left half [5, -7]: subset sums [0, 5, -7, -2]
3. Right half [3, 5]: subset sums sorted [0, 3, 5, 8]
4. left 0: need 6; nearest right sum 5 → |5 − 6| = 1
5. left 5: need 1; nearest right sum 0 → |5 − 6| = 1
6. left -7: need 13; nearest right sum 8 → |1 − 6| = 5
7. left -2: need 8; nearest right sum 8 → |6 − 6| = 0
8. Closest subsequence sum differs from the goal by 0
9. Enumerate 2^(n/2) per side, binary search to match: O(2^(n/2) · n)

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Advanced Structures: Segment tree (range query + point update), Fenwick tree (binary indexed tree), Ordered set / sorted container, Bucketing by value range, Matrix exponentiation for recurrences.