ii. Meet in the Middle

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 \leq 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 1 0^{6}$ per half — instant.

Proof: subsetSum is correct

Every subset of the full $n$ items is, by construction, the union of a subset of the first $h$ items and a subset of the remaining $n - h$ items, and these two parts are chosen completely independently — so enumerating every subset of each half and taking every pair $(x, y)$ with $x \in A, y \in B$ covers every subset of the whole exactly once (as $x + y$ ). The algorithm checks, for every $x \in A$ , whether $S - x$ appears in $B$ — i.e. whether some pair sums to exactly $S$ — which by the above is exactly “does some subset of the full set sum to $S$ ”. Splitting $n$ into two halves of size $h$ and $n - h$ reduces $O (2^{n})$ enumeration to $O (2^{h} + 2^{n - h})$ , minimised at $h = n /2$ . $■$

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 $\leq 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 $\leq 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.

Proof: the prefix-maximum trick

After sorting $B$ by weight, “the best value achievable using some item of $B$ with weight $\leq w$ ” is, by definition, $max {B [i] . v a l u e : B [i] . w e i g h t \leq w}$ — a maximum over a prefix of the sorted array (every item with weight $\leq w$ appears before the first item with weight $> w$ ). Taking the running prefix maximum in sorted order precomputes exactly this quantity at every array position, so after the transform, B[i].value (the new, overwritten value) already equals that prefix maximum — and a single lower_bound to find the rightmost index with weight $\leq w$ , followed by reading B[i].value there, answers the query in $O (lo g n)$ instead of needing a range-maximum structure.

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 \leq 500$	pair sums from each half, $O (n^{2})$
Shortest path with $\leq k$ edges		bidirectional BFS
Discrete log (baby-step giant-step)		$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 $2 k$ 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 1 0^{4}$	0.3 MB
40	$1.0 \cdot 1 0^{6}$	8 MB
44	$4.2 \cdot 1 0^{6}$	34 MB
50	$3.4 \cdot 1 0^{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.

Bidirectional Search

Search simultaneously from the start and from the goal, stopping when the frontiers meet. With branching factor $b$ and distance $d$ , a one-sided BFS explores $O (b^{d})$ states, while bidirectional explores $O (2 b^{d /2})$ . That’s the difference between impossible and instant for puzzles.

Requirements

The goal state is known explicitly (not just a predicate).
Moves are reversible, or you can generate predecessors.
States are hashable (store visited sets in hash maps).

Algorithm (unweighted)

BFS frontiers $F_{s} = {s}$ , $F_{t} = {t}$ with distance maps $d_{s}$ , $d_{t}$ .
Always expand the smaller frontier by one full layer.
When a newly generated state $v$ exists in the other side’s map, the answer is $d_{s} (v) + d_{t} (v)$ (minimise over the whole layer).

int bidirectional(State s, State t) {
    if (s == t) return 0;
    unordered_map<State, int> ds{{s, 0}}, dt{{t, 0}};
    vector<State> fs{s}, ft{t};
    while (!fs.empty() && !ft.empty()) {
        bool fromS = fs.size() <= ft.size();
        auto& F = fromS ? fs : ft;
        auto& D = fromS ? ds : dt;
        auto& O = fromS ? dt : ds;
        vector<State> nxt;
        int best = INT_MAX;
        for (auto& u : F) for (auto& v : neighbours(u)) {   // predecessors if expanding from t in a directed space
            if (D.count(v)) continue;
            D[v] = D[u] + 1;
            if (O.count(v)) best = min(best, D[v] + O[v]);
            nxt.push_back(v);
        }
        if (best != INT_MAX) return best;
        F.swap(nxt);
    }
    return -1;
}

Relation to meet in the middle

Meet in the Middle is the same idea for non-graph enumeration: split the choices into two halves, enumerate each, and combine via sorting or hashing.

Weighted version

Run Dijkstra from both sides alternately. Stop when $top_{s} + top_{t} \geq μ$ , where $μ$ is the best meeting distance found so far.

Pitfalls

Stopping at the first meeting vertex without finishing the layer can give a non-shortest answer in edge cases. Finish the layer.
Memory: both hash maps hold $O (b^{d /2})$ states.
Typical uses: 15-puzzle variants, Rubik’s-cube-like puzzles, word ladders, permutation sorting by reversals with small $n$ .

Proof: bidirectional BFS finds the shortest path, and why a full layer must finish

Correctness. If the true shortest distance is $μ$ , some vertex $v$ on a shortest $s \to t$ path has $d_{s} (v) + d_{t} (v) = μ$ exactly (take $v$ at or near the midpoint of any shortest path — more precisely, as both BFS frontiers expand layer by layer, consider the first moment either frontier reaches a vertex on a fixed shortest path; by a pigeonhole argument on the path’s own length $μ$ , some vertex of that path is discovered by one side while its distance from the other side, via the same path, is still consistent, giving a candidate summing to exactly $μ$ once both sides have explored far enough). No pair $(v, d_{s} (v) + d_{t} (v))$ can sum to less than $μ$ , since $d_{s} (v)$ and $d_{t} (v)$ are true shortest distances in their respective directions and any $s \to v \to t$ walk has length $\geq μ$ (the true shortest path length) by definition of $μ$ . So the minimum over all common vertices found is exactly $μ$ .
Why the layer must finish. The algorithm only has a candidate upper bound best once some common vertex is found mid-layer; a vertex discovered later in the same layer expansion (before swapping to the next layer) could still realize a smaller $d_{s} (v) + d_{t} (v)$ sum, since the layer being expanded contains many vertices at the same new distance, and the true minimum might be realized by one processed later in the same batch. Stopping at the very first match found (rather than completing the current layer’s full expansion and taking the minimum over all matches in it) risks returning a non-optimal sum. $■$

whoashish's cp notes

Directory