Meet in the Middle

Split the input in half, enumerate each half separately, and combine. Turns $O(2^n)$ into $O(2^{n/2})$ — the difference between $n=25$ and $n=45$.

The pattern

1. Split the n items into halves A and B.
2. Enumerate all 2^(n/2) subsets of A, storing their values.
3. Enumerate all 2^(n/2) subsets of B; for each, find the matching partner in A.

The combine step is a sort + binary search, a hash map, or a two-pointer scan.

Worked example: subset sum

“Is there a subset summing to exactly $S$?” with $n\le 40$.

bool subsetSum(vector<long long>& a, long long S) {
    int n = a.size(), h = n / 2;
    vector<long long> A, B;
    for (int m = 0; m < (1 << h); m++) {
        long long s = 0;
        for (int i = 0; i < h; i++) if (m >> i & 1) s += a[i];
        A.push_back(s);
    }
    for (int m = 0; m < (1 << (n - h)); m++) {
        long long s = 0;
        for (int i = 0; i < n - h; i++) if (m >> i & 1) s += a[h + i];
        B.push_back(s);
    }
    sort(B.begin(), B.end());
    for (long long x : A)
        if (binary_search(B.begin(), B.end(), S - x)) return true;
    return false;
}

$O(2^{n/2}\cdot n)$ time and $O(2^{n/2})$ memory. For $n=40$ that is $\approx 10^6$ per half — instant.

The variants of the combine step

Goal	Combine
Exact sum $S$	hash set, or sort + binary search
Closest to $S$	sort $B$, lower_bound and check both neighbours
Sum $\le S$, maximise	sort $B$, keep a prefix maximum, binary search
Count the ways	sort $B$, equal_range
Sum in a range	two lower_bound calls
Maximise a value under a weight limit	sort $B$ by weight, prefix-max the value, binary search
Both halves constrained	sort both, two pointers

The prefix-maximum trick

For “maximise the value with total weight $\le W$”:

sort(B.begin(), B.end());                              // by weight
for (int i = 1; i < (int)B.size(); i++)
    B[i].value = max(B[i].value, B[i-1].value);        // prefix max
// then for each a in A: binary search the largest weight <= W - a.weight

Without the prefix maximum you would need the maximum over a range; with it, the binary search alone suffices.

Where it applies

Problem	$n$	Note
Subset sum / partition	40-45	the canonical case
Knapsack with huge weights	40	when the DP’s $W$ is too large
Count subsets with a given XOR	40	hash map on the XOR
4-SUM	$n\le 500$	pair sums from each half, $O(n^2)$
Shortest path with $\le k$ edges		bidirectional BFS
Discrete log (baby-step giant-step)		$\sqrt{m}$ from each side
Solve $a^x=b$, $x^k=a$		the same splitting
Puzzle solving (15-puzzle, Rubik’s)		bidirectional BFS
Count paths of length $2k$ in a graph		meet at the midpoint
Equation $f(x)+g(y)=c$		enumerate each side

Bidirectional search — the graph version

Search forward from the start and backward from the goal, stopping when the frontiers meet:

$O(b^d)⟶O(b^{d/2}).$

// BFS from both ends, always expanding the smaller frontier
while (!fwd.empty() && !bwd.empty()) {
    if (fwd.size() <= bwd.size()) expand(fwd, visitedF, visitedB, ans);
    else                          expand(bwd, visitedB, visitedF, ans);
}

Expanding the smaller frontier keeps the balance. This is what makes the 15-puzzle and similar state-space searches tractable.

Memory — the real constraint

$2^{n/2}$ entries at 8 bytes:

$n$	Entries per half	Memory
30	$3.3\cdot 10^4$	0.3 MB
40	$1.0\cdot 10^6$	8 MB
44	$4.2\cdot 10^6$	34 MB
50	$3.4\cdot 10^7$	268 MB — too much

Mitigations: store only one half and stream the other; use an unequal split (a smaller stored half); or apply Schroeppel-Shamir, which solves subset sum in $O(2^{n/2})$ time but only $O(2^{n/4})$ memory by splitting into four parts and merging with priority queues.

Choosing the split

An even split minimises $\max (2^a,2^{n-a})$. But if one side’s enumeration is cheaper or its combine step is heavier, shifting the split can help. When memory is the binding constraint, store the smaller half.

See also: Subset Sum · Branch and Bound · Discrete Logarithm