Meet-in-the-Middle
Split an exponential search into two smaller exponential searches and join the halves with sorting or hashing.
Meet-in-the-Middle
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Meet-in-the-middle is the standard response to ``the search space is exponential, but \(n\) is only around 40.'' It does not remove exponential behavior. It cuts the exponent in half and then combines the two halves intelligently.
Problem-Driven Motivation
Suppose a subset problem has \(n = 40\). A full brute force explores \(2^{40}\) states, which is completely out of reach. But \(2^{20}\) is only about one million. That difference is the entire point of the technique:
This shows up in subset sum, balanced partition, small-set knapsack, and other ``combine one choice from the left half with one choice from the right half'' problems.
Recognition Pattern
Meet-in-the-middle is a strong candidate when:
\(n\) is roughly \(30\) to \(46\),
the direct search is exponential in \(n\),
a full solution decomposes into an independent left-half choice and right-half choice,
DP by total sum or total value is impossible because the numeric limit is too large.
The phrase I look for is:
Can I summarize each half independently, then search for a compatible partner?
Derivation
Split the items into two halves: \[ L = \{a_0,\dots,a_{m-1}\},\qquad R = \{a_m,\dots,a_{n-1}\}. \]
Enumerate every subset summary of \(L\) and every subset summary of \(R\). The summary could be:
subset sum,
weight-value pair,
mask property,
any compressed state that combines cleanly.
Once those lists are built, the problem is no longer ``search over all \(2^n\) subsets.'' It is ``combine one left summary with one right summary.''
The merge step is where the real structure of the problem appears:
sort + binary search for subset sum bounds,
two pointers for monotone pairing,
hash map for exact complements,
dominance pruning for multi-attribute summaries.
Worked Problem
Problem.
Given \(n \le 40\) positive integers and a limit \(S\), find the largest subset sum not exceeding \(S\).
Why the naive solution fails.
Enumerating all subsets is \(O(2^n)\), which is too large for \(n=40\).
Step 1: split and enumerate.
Generate all subset sums of the left half and all subset sums of the right half.
Step 2: sort one side.
Sort all right-half sums.
Step 3: combine.
For every left-half sum \(x\), the best partner is the largest right-half sum \(y\) satisfying \[ x + y \le S. \] That partner is found by upper_bound.
Why this covers all subsets.
Every full subset is uniquely the union of:
one subset of the left half,
one subset of the right half.
So checking all left summaries against all compatible right summaries explores the entire solution space.
Implementation Reasoning
The main implementation decisions are:
store all half sums explicitly,
reserve memory for \(2^{n/2}\) elements to avoid repeated reallocations,
use sorting and binary search because the merge condition is an upper bound.
In more complex problems, the important refinement is usually pruning. If one summary dominates another in all relevant coordinates, the dominated summary can be discarded before the merge.
Correctness Intuition
The split does not approximate anything. It is exact. The only reason it is faster is that combining two half-spaces is much cheaper than enumerating the full space directly.
Complexity Analysis
For the subset-sum version:
enumerate both halves: \(O(2^{n/2})\),
sort one half: \(O(2^{n/2}\log 2^{n/2})\),
binary-search combine: \(O(2^{n/2}\log 2^{n/2})\),
memory: \(O(2^{n/2})\).
Common Pitfalls
Using meet-in-the-middle when a simpler pseudo-polynomial DP is already better.
Forgetting the memory cost of storing every half summary.
Generating the half summaries correctly but combining them with the wrong inequality or off-by-one boundary.
Missing a dominance-pruning step in a two-dimensional summary problem.
Variants and Failure Modes
Exact subset-sum queries usually replace sorting with hashing by complement.
Two-attribute problems often sort one side and keep only Pareto-optimal summaries.
If \(n\) is much larger than 45, halving the exponent is still not enough.
Practice Problems
Maximum subset sum not exceeding a limit.
Closest subset sum to a target.
Pairing one left-half state with one right-half state under a compatibility constraint.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
vector<long long> subset_sums(const vector<long long>& a) {
int n = (int)a.size();
vector<long long> sums;
sums.reserve(1 << n);
for (int mask = 0; mask < (1 << n); ++mask) {
long long total = 0;
for (int bit = 0; bit < n; ++bit) {
if ((mask >> bit) & 1) total += a[bit];
}
sums.push_back(total);
}
return sums;
}
// Example application: maximum subset sum not exceeding limit.
long long max_subset_sum_at_most(const vector<long long>& a, long long limit) {
int n = (int)a.size();
int mid = n / 2;
vector<long long> left(a.begin(), a.begin() + mid);
vector<long long> right(a.begin() + mid, a.end());
vector<long long> left_sums = subset_sums(left);
vector<long long> right_sums = subset_sums(right);
sort(right_sums.begin(), right_sums.end());
long long answer = 0;
for (long long x : left_sums) {
if (x > limit) continue;
auto it = upper_bound(right_sums.begin(), right_sums.end(), limit - x);
if (it != right_sums.begin()) {
--it;
answer = max(answer, x + *it);
}
}
return answer;
}
// Another common application: exact target via hashing instead of sorting + upper_bound.
bool subset_sum_exact_target(const vector<long long>& a, long long target) {
int n = (int)a.size();
int mid = n / 2;
vector<long long> left(a.begin(), a.begin() + mid);
vector<long long> right(a.begin() + mid, a.end());
vector<long long> left_sums = subset_sums(left);
unordered_set<long long> wanted;
wanted.reserve(left_sums.size() * 2);
for (long long x : left_sums) wanted.insert(target - x);
for (long long y : subset_sums(right)) {
if (wanted.count(y)) return true;
}
return false;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.