Meet in the Middle

Why meet in the middle matters

Many combinatorial problems are trivially solvable by trying every possibility — but "every possibility" is 2ⁿ, and 2ⁿ grows so fast that even n = 45 is out of reach on a single machine (2⁴⁵ ≈ 3.5 × 10¹³ operations, minutes to hours). Meet in the middle exploits a structural gift: when the n decisions are independent binary choices, you can decide the first half and the second half separately, then merge the results. Each half has only 2^(n/2) outcomes. Since 2^(n/2) = √(2ⁿ), you replace an exponent with half an exponent — the square root of the original work.

Concretely: for n = 40, brute force is 2⁴⁰ ≈ 1.1 × 10¹² (a trillion, too slow). Meet in the middle is 2²⁰ ≈ 10⁶ per half — a million operations, essentially instant. That single doubling of tractable input size, from n ≈ 25 to n ≈ 50, is the difference between "unsolvable" and "solved in a millisecond" for an entire family of NP-hard-flavored problems: subset sum, k-sum, partition, minimum-cost knapsack with tiny item counts, and finding four values that XOR to zero.

How it works, step by step

Take the canonical problem: subset sum — given n integers and a target T, does some subset sum exactly to T? The naive approach enumerates all 2ⁿ subsets. Meet in the middle proceeds:

1. Split. Partition the n numbers into two halves, L (first n/2 numbers) and R (last n/2). This split is arbitrary — any balanced partition works.
2. Enumerate each half. Compute the multiset of all subset sums of L — there are 2^(n/2) of them. Do the same for R. Each list is generated in O(2^(n/2)) time by iterating over bitmasks or by recursion.
3. Prepare one side. Sort the list of R-sums (or insert them into a hash set). Sorting costs O(2^(n/2) · log 2^(n/2)) = O(2^(n/2) · n).
4. Combine. For each sum a in the L-list, look for the complement T − a in the R-list via binary search (or a hash probe). If found, the corresponding subset of L plus subset of R together sum to exactly T.

The genius is in step 4. Instead of pairing every L-subset with every R-subset (which would be 2^(n/2) × 2^(n/2) = 2ⁿ — back to brute force), you let the value do the matching. Each a has exactly one complement T − a, and binary search finds whether that complement exists in O(log 2^(n/2)) = O(n) time. The cross product never materializes.

The same skeleton adapts to many objectives. Want the subset sum closest to T without exceeding it? Sort R, and for each a use upper_bound(T − a) to find the largest feasible R-sum — the predecessor query a hash table cannot answer. Want to count subsets hitting T? Sort R and, for each a, count occurrences of T − a with a pair of binary searches.

Complexity: why √(2ⁿ)

Let n be the number of elements. Splitting gives two halves of n/2 elements, each yielding 2^(n/2) sub-results.

• Enumeration: O(2^(n/2)) per half — 2·2^(n/2) = O(2^(n/2)) total.
• Sorting one half: O(2^(n/2) · log(2^(n/2))) = O(2^(n/2) · (n/2)) = O(2^(n/2) · n).
• Combining: 2^(n/2) binary searches, each O(n), so O(2^(n/2) · n).
• Total time: O(2^(n/2) · n) with sorting, or O(2^(n/2)) expected with hashing.
• Total space: O(2^(n/2)) — you must store at least one full half's results.

Because 2^(n/2) = (2ⁿ)^(1/2), the running time is the square root of the brute-force baseline (ignoring the polynomial n factor). This is the same "exponent-halving" you see in bidirectional graph search, baby-step giant-step for discrete logarithms, and the generalized birthday problem — all cousins of meet in the middle.

Meet in the middle vs brute force vs DP

	Brute force	Meet in the middle	Pseudo-poly DP
Time	O(2ⁿ)	O(2^(n/2) · n)	O(n · T)
Space	O(n)	O(2^(n/2))	O(T) or O(n · T)
Good when	n ≤ 25	n ≤ 40–45, any values	T small (integer)
Handles huge / real values?	Yes	Yes	No (needs integer T)
Handles large n?	No	No (2^(n/2) blows up)	Yes (if T is bounded)
Extra memory cost	None	High (stores a half)	Proportional to T

The decision rule is clean. If the target/weights are small integers, use the pseudo-polynomial DP — it is simpler and faster. If n is small but the values are astronomically large (up to 10¹⁸) or real-valued, DP's table is infeasible and meet in the middle wins. If n is large (say ≥ 60), neither exact method fits in memory and you fall back to approximation or specialized lattice methods.

Implementation in Python: subset sum

from bisect import bisect_left, insort

def subset_sum_exists(nums, target):
    """Return True if some subset of nums sums exactly to target.
    Runs in O(2^(n/2) * n) time and O(2^(n/2)) space."""
    n = len(nums)
    mid = n // 2
    left, right = nums[:mid], nums[mid:]

    def all_subset_sums(arr):
        sums = [0]
        for x in arr:
            sums += [s + x for s in sums]   # doubles the list each step
        return sums

    left_sums = all_subset_sums(left)        # 2^(mid) values
    right_sums = sorted(all_subset_sums(right))  # 2^(n-mid) values, sorted

    for a in left_sums:
        need = target - a
        i = bisect_left(right_sums, need)
        if i < len(right_sums) and right_sums[i] == need:
            return True
    return False


def closest_subset_sum(nums, target):
    """Largest achievable subset sum that does not exceed target."""
    n = len(nums)
    mid = n // 2
    left_sums = _sums(nums[:mid])
    right_sums = sorted(_sums(nums[mid:]))
    best = float('-inf')
    for a in left_sums:
        room = target - a
        i = bisect_left(right_sums, room + 1) - 1  # largest R-sum <= room
        if i >= 0:
            best = max(best, a + right_sums[i])
    return best

def _sums(arr):
    sums = [0]
    for x in arr:
        sums += [s + x for s in sums]
    return sums

The all_subset_sums helper doubles its output on each iteration, so after processing all n/2 elements it holds exactly 2^(n/2) sums. Sorting the right half once, then binary-searching it 2^(n/2) times, is what keeps the combine step off the 2ⁿ cross product. For the pure existence test you can swap the sorted array + bisect for a Python set and get O(2^(n/2)) expected time — but you lose the predecessor query that closest_subset_sum depends on.

A short history: subset sum and Double DES

The first published meet-in-the-middle algorithm is due to Ellis Horowitz and Sartaj Sahni in 1974, "Computing Partitions with Applications to the Knapsack Problem." They solved subset sum and 0/1 knapsack in O(2^(n/2)) time and space — a landmark because it showed that a problem believed to require 2ⁿ effort could be square-rooted with clever bookkeeping.

Three years later, in 1977, Whitfield Diffie and Martin Hellman turned the same idea into a cryptanalytic weapon. Their target was Double DES: encrypting a block twice under two independent 56-bit keys, C = E(k₂, E(k₁, P)), which naively looks like 112-bit security (2¹¹² keys). Diffie and Hellman observed that the intermediate value M = E(k₁, P) = D(k₂, C) is the "middle" both sides can compute. Encrypt a known plaintext under all 2⁵⁶ values of k₁ and store the results; decrypt the known ciphertext under all 2⁵⁶ values of k₂; any collision in the middle reveals a candidate (k₁, k₂). The attack costs about 2⁵⁷ encryptions and 2⁵⁶ storage instead of 2¹¹². This is precisely why the world standardized on Triple DES (three DES operations, effective ~112-bit security even under meet in the middle) rather than Double DES. The same principle attacks other cascade ciphers and drives collision-finding across cryptography.

Common misconceptions and pitfalls

• "It makes exponential problems polynomial." No — 2^(n/2) is still exponential. Meet in the middle roughly doubles the feasible input size; it does not defeat NP-hardness. For n = 80 it needs 2⁴⁰ ≈ 10¹² entries, which no longer fits in memory.
• Forgetting the memory wall. The technique lives or dies on whether 2^(n/2) results fit in RAM. At n = 50 that is 2²⁵ ≈ 33 million entries (fine); at n = 60 it is 2³⁰ ≈ 10⁹ (gigabytes, borderline); at n = 66 it is 2³³ ≈ 8 × 10⁹ (usually too much). Always compute the storage before committing.
• Materializing the cross product. The whole point is to match by value, never pairing every L-subset with every R-subset. If your combine loop is nested over both lists, you have reintroduced O(2ⁿ) and gained nothing.
• Unbalanced split. Splitting 1/3 vs 2/3 gives 2^(n/3) + 2^(2n/3) — dominated by the larger half. Always split as evenly as possible to minimize the max of the two halves.
• Hashing when you need order. A hash set answers "does exactly T − a exist?" but not "what is the largest R-sum ≤ T − a?" For closest-sum, count-in-range, or bounded-knapsack variants you need a sorted array and binary search (or a balanced BST).
• Integer overflow. Subset sums of large inputs can exceed 32-bit and even 64-bit ranges; use wide integers and be deliberate about the target's type.

Where it shows up

• Subset sum & partition. The classic use: decide if a target is reachable, or find the closest reachable sum, for n up to ~40. Competitive programming problems with n ≤ 40 and 64-bit weights are a dead giveaway for meet in the middle.
• 4-SUM and k-SUM. Finding four numbers summing to T: enumerate all pairwise sums from two halves in O(N²), sort, and match — an O(N² log N) algorithm that is a two-list meet in the middle over pairs.
• Cryptanalysis. Double encryption, multi-key cascades, and hash collision search all use the encrypt-forward / decrypt-backward meeting pattern; it is the reason effective key length of a double cipher is only slightly more than a single one.
• Discrete logarithm — baby-step giant-step. Shanks's algorithm solves gˣ = h in O(√N) time and O(√N) space by tabulating "baby steps" and matching against "giant steps" — meet in the middle over a cyclic group.
• Minimum-cost path / bounded search. When a search tree has depth d and branching b, meeting from both ends turns O(b^d) into O(b^(d/2)) — the bidirectional-search sibling of this idea.