Meet in the Middle, in depth: splitting 2^n into two 2^(n/2) searches, joins, bidirectional search and the double-DES attack

Split, enumerate, join

The pattern has three steps. Split the decision variables into two halves. Enumerate every partial solution of each half and summarise it by the value the other half needs to know, usually a sum or a state. Join the two lists with a lookup that is cheaper than trying every pair: sorting plus binary search, two pointers, or a hash map.

It works only when the objective decomposes: the value of a full solution must be computable from one number or state per half. Subset sum decomposes because total = left sum + right sum. Knapsack decomposes with a pair (weight, value) per half. A problem whose constraints couple the halves in complicated ways, such as ordering constraints that cross the split, either needs a richer summary or does not split at all.

Recognising the pattern is half the skill. The strongest hint is a constraint like n up to 40 with values up to 10⁹ or more: too many items for brute force, numbers too large for a dynamic programming table, and 2²⁰ sitting comfortably in memory. Other hints are a sum of four terms from four lists, where you pair the lists into two sums of two and join (an O(N²) answer to a problem that looks O(N⁴)); a reversible process with a known start and end; and a composite of two independent stages, each with its own secret or choice, where the intermediate value can be computed from both sides.

The cost model and the memory wall

Enumerating one half costs 2^n/2 steps if you build sums incrementally. Sorting one list adds a log factor, and the join does 2^n/2 lookups. Memory is what usually stops you, because at least one full half must be stored.

Around n = 40 the technique is comfortable in any language. At n = 50 it fits in memory but needs compact arrays (NumPy or C++, not Python lists of int objects, which cost several times more per element). At n = 60 the stored half becomes the bottleneck, and you need the memory-saving variant described below or a different algorithm.

Joins that make it work

Generate sums in sorted order without sorting. Start with the list [0]. For each item x in the half, merge the current sorted list with the same list shifted by x. Each step doubles the list and stays sorted, and the total work is O(2^n/2) rather than O(2^n/2 n), which beats generating by bitmask and then sorting.

from bisect import bisect_right
from collections import Counter

def sorted_sums(items):
    sums = [0]
    for x in items:
        shifted = [s + x for s in sums]
        merged, i, j = [], 0, 0
        while i < len(sums) and j < len(shifted):
            if sums[i] <= shifted[j]:
                merged.append(sums[i]); i += 1
            else:
                merged.append(shifted[j]); j += 1
        merged.extend(sums[i:]); merged.extend(shifted[j:])
        sums = merged
    return sums

def count_exact(items, target):
    half = len(items) // 2
    left = sorted_sums(items[:half])
    right = Counter(sorted_sums(items[half:]))  # duplicates counted, not collapsed
    return sum(right[target - a] for a in left)

def best_at_most(items, cap):
    half = len(items) // 2
    left, right = sorted_sums(items[:half]), sorted_sums(items[half:])
    best = None
    for a in left:
        k = bisect_right(right, cap - a) - 1     # largest b with a + b <= cap
        if k >= 0 and (best is None or a + right[k] > best):
            best = a + right[k]
    return best

Three join strategies cover most problems. A hash map of counts answers exact-match questions, and counting rather than storing a set is what makes duplicates come out right: if two different right subsets both sum to 7, each pairs separately with a matching left subset. Binary search answers best-within-a-cap questions. Two pointers, one ascending through the left list and one descending through the right, answers closest-to-target questions in a single linear pass over both sorted lists.

For knapsack with weights and values, each half produces (weight, value) pairs. Sort the right half by weight, drop dominated pairs (heavier but not more valuable) so values increase with weight, then for each left pair binary-search the heaviest right pair that fits the remaining capacity.

Worked example: six numbers by hand

Count subsets of [3, 34, 4, 12, 5, 2] that sum to 9. Split into left [3, 34, 4] and right [12, 5, 2].

For each left sum a, look up 9 - a in the right multiset. Left 0 needs 9: absent. Left 3 needs 6: absent. Left 4 needs 5: present, giving {4, 5}. Left 7 needs 2: present, giving {3, 4, 2}. Every larger left sum needs a negative partner. The answer is 2, from 8 + 8 = 16 enumerated sums instead of 64 subsets. The saving is modest here and enormous at n = 40, where it is 2 million instead of a trillion.

A quick sanity check is worth keeping in your tests: a brute-force counter over all 2ⁿ subsets for n up to about 20, compared against the meet-in-the-middle answer on random inputs with many repeated values and negative numbers. Repeated values are what catch set-based joins that silently undercount.

Bidirectional search is the same idea

Meet in the middle is not only for sums. In a state-space search with branching factor b and solution depth d, breadth-first search from the start explores about b^d states. Searching from both the start and the goal and stopping when the frontiers meet explores about 2 b^d/2. For a sliding puzzle or a word ladder, that difference decides whether the search finishes. It needs an invertible move set, so you can step backwards from the goal.

def bidirectional_bfs(start, goal, neighbors):
    if start == goal:
        return 0
    dist_s, dist_g = {start: 0}, {goal: 0}
    front_s, front_g = [start], [goal]
    while front_s and front_g:
        # always expand the smaller frontier
        if len(front_s) > len(front_g):
            front_s, front_g, dist_s, dist_g = front_g, front_s, dist_g, dist_s
        best, nxt = None, []
        for u in front_s:                       # finish the whole layer
            for v in neighbors(u):
                if v in dist_s:
                    continue
                dist_s[v] = dist_s[u] + 1
                if v in dist_g:
                    cand = dist_s[v] + dist_g[v]
                    best = cand if best is None else min(best, cand)
                nxt.append(v)
        if best is not None:
            return best
        front_s = nxt
    return -1

The subtle point is in the inner loop: stop only after the whole layer is expanded, then take the minimum over all meeting points. Returning at the first meeting can report a path longer than the shortest. The graph modelling side, how to turn a puzzle into states and moves, is covered in BFS on implicit graphs.

Double DES and the memory-saving variant

The most famous use is cryptanalytic. DES has a 56-bit key, so it seemed natural to encrypt twice with two independent keys and expect 112 bits of security. Meet in the middle shows otherwise. Given one known plaintext P and its ciphertext C, encrypt P under all 2⁵⁶ first keys and store the results in a table. Then decrypt C under all 2⁵⁶ second keys and look each result up. Any match is a candidate key pair, and a second known pair weeds out false matches. The cost is about 2⁵⁷ cipher operations plus a table of 2⁵⁶ entries, not 2¹¹². That is why Triple DES, not Double DES, became the standard fix, and why any cascade of two independent ciphers should be assumed to give little more than the strength of one plus a large memory cost for the attacker.

The memory requirement is the attacker's real obstacle, and it motivates the general memory-saving variant. The Schroeppel-Shamir algorithm solves subset-sum-style problems in O(2^n/2) time but only O(2^n/4) memory by splitting into four quarters and generating each half's sums lazily, in sorted order, with priority queues. For n = 60 that turns an 8 GiB table into lists of about 32,768 entries, at the cost of heap overhead and a more intricate implementation.

Failure modes

• Out of memory before out of time. Python lists of ints cost several times the raw 8 bytes per element; n = 50 can exhaust a laptop. Use NumPy int64 arrays or C++ vectors, or switch to Schroeppel-Shamir.
• Undercounting with sets. Collapsing duplicate sums into a set gives wrong counts. Use a counter or sorted runs.
• Missing the empty subset. Both halves must include sum 0 or solutions that use only one half disappear. Decide whether the empty overall subset counts, as counting subsets discusses.
• Overflow. Values near 10¹² summed over 20 items fit in 64 bits, but products or weighted sums may not.
• Unbalanced split. Halves of 15 and 25 store 2²⁵ entries instead of 2²⁰. Split evenly, or put the larger half on the side you stream rather than store.
• Quadratic join. Comparing every left sum with every right sum is 2ⁿ again. The join must be a lookup.

Trade-offs: when to use something else

The deciding question is which is small: the number of items or the magnitude of the numbers. If it is the numbers, use dynamic programming, as in the knapsack problem and target sum by sign assignment. If it is the items, meet in the middle. Hash-based joins depend on a good hash table; see hash tables for load factor and collision behaviour.

What to do next

1. Implement sorted_sums and count_exact, and verify them against brute force on random lists of length 1 to 20 with repeats and negatives.
2. Time n = 40 with values up to 10¹²; then port the inner loops to NumPy or C++ and measure memory at n = 50.
3. Add best_at_most and a two-pointer closest-sum variant, and test both at the edges: cap below every item, cap above the total.
4. Solve a knapsack instance with 40 items and huge weights using dominance pruning on the right half.
5. Write bidirectional BFS for a word ladder and confirm it returns the same distances as one-sided BFS.
6. Read the Schroeppel-Shamir construction and sketch how the four quarter lists are merged with heaps.