Meet in the Middle: Turning 2^n Into 2^(n/2) in Coding Interviews

Constraints are a hint. When a problem says n ≤ 40 and asks about subsets, 2^40 is about a trillion: too slow. But 2^20 is about a million, which is fast. Meet in the middle exploits exactly that gap.

The pattern

1. Split the items into two halves A and B.
2. Enumerate every subset of each half (2^(n/2) each) and record what matters, such as the sum.
3. Combine: for each value from A, find the best matching value from B using sorting with binary search, two pointers or a hash map.

Example: closest subset sum to a target

from bisect import bisect_left

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

def closest_subset_sum(nums, target):
    half = len(nums) // 2
    left, right = sums(nums[:half]), sorted(sums(nums[half:]))
    best = float("inf")
    for s in left:
        need = target - s
        i = bisect_left(right, need)
        for j in (i - 1, i):
            if 0 <= j < len(right):
                best = min(best, abs(s + right[j] - target))
    return best

Complexity: O(2^(n/2) · n) time and O(2^(n/2)) memory, versus O(2^n) for plain brute force.

Variations worth knowing

• Count subsets with sum ≤ S: sort one side, use two pointers across both sorted lists.
• 4-sum style problems: pair sums from two arrays into a hash map, then look up the complement from the other two arrays, for O(n²) instead of O(n⁴).
• Bidirectional BFS: the graph version, searching from the start and the goal until the frontiers meet, which shrinks b^d to 2·b^(d/2).

Pitfalls

• Memory: 2^20 integers is fine, but storing full subsets instead of sums can blow up.
• Off-by-one at the split for odd n: it doesn't matter for correctness, just keep the halves near equal.
• Duplicates in counting problems: use counts (or bisect_right - bisect_left) rather than assuming unique sums.

Interview framing: "n is 40, so I'll split into two halves of 20, enumerate a million sums per side, sort one side, and binary search the complement."

Disclosure: I work on Linkjob.ai, an AI coding interview assistant. Notes are general study material.