Meet in the Middle

A technique that halves the exponent of brute force by splitting the search, solving both halves, and combining results.

The idea

Meet in the middle attacks problems whose brute force is 2^n by splitting the input into two halves of size n/2, enumerating all 2^(n/2) possibilities for each, and combining the two lists cleverly. This turns 2^n into roughly 2^(n/2) time, at the cost of storing one half, making instances up to about n = 40 tractable that were hopeless at n = 40 directly.

Subset-sum example

Kronos motion — meet hyperion

To decide whether any subset of n numbers sums to a target, enumerate all subset sums of the first half and sort them, then for each subset sum of the second half binary-search for the complement. Each half has 2^(n/2) subsets, so the total is O(2^(n/2) * n), a dramatic improvement over 2^n.

Sketch

python

from bisect import bisect_left

def subset_sum(nums, target):
    n = len(nums); half = n // 2
    def sums(arr):
        out = [0]
        for x in arr:
            out += [s + x for s in out]
        return out
    left = sorted(sums(nums[:half]))
    for s in sums(nums[half:]):
        need = target - s
        i = bisect_left(left, need)
        if i < len(left) and left[i] == need:
            return True
    return False

Where it applies

Subset sum, partition, and knapsack with small n but large weights.
Discrete logarithm via the baby-step giant-step algorithm, a meet-in-the-middle over exponents.
Solving equations by enumerating each side independently.
4-sum and k-sum problems by pairing halves.

Trade-off

Meet in the middle trades exponential time for exponential space in the smaller exponent. It is the natural next step when a problem is too big for brute force but too general for a polynomial or pseudo-polynomial dynamic program.