Vibe Engines Learn
Algorithms · Exponential Search

Meet in the Middle.

Does any subset of these numbers add up to the target? Trying every subset is 2ⁿ — hopeless past ~30 items. But split the set in two, enumerate each half’s subset sums separately, and the two halves can shake hands: for every sum on the left, look for its complement on the right. Exponential work becomes its own square root — 2ⁿ → 2·2^(n/2).

O(2^(n/2)) time · square-root speedup · subset-sum
split in two

Halve the set; solve each half independently.

half-sums

Enumerate all 2^(n/2) subset sums of each half.

complement

For a left sum s, seek target − s among the right sums.

handshake

A left subset + a right subset that together hit the target.

mitm.js — enumerate halves, match complements
target sum: 9 16 21 100
Ready
The set is split into a left and right half. We list every subset sum of each. Press Step: for each left sum s, we look for target − s in the right sums — a match means a subset hits the target.
–
left sum s
–
need t−s
–
vs brute 2ⁿ

How it works

The problem is exponential because a subset is a yes/no choice per item — 2ⁿ combinations. The trick: those choices split cleanly. Whatever the left half contributes, the right half must contribute exactly target − (left sum). So you never need to pair every left subset with every right subset (that would be 2ⁿ again) — you just look up the needed complement.

1

Split the set in half

n items → two halves of n/2. Each half has only 2^(n/2) subsets — exponentially fewer.

2

Enumerate each half’s sums

List all subset sums of the left half and all of the right half. Store the right sums in a hash set (or sort them).

3

Match complements

For each left sum s, check if target − s is a right sum. A hit means left-subset + right-subset = target.

✓

Square-root win

Total work ≈ 2·2^(n/2) instead of 2ⁿ. For n = 40: ~10⁶ vs ~10¹² — a million times faster.

Time
O(2^(n/2))
Brute force
O(2ⁿ)
Space
O(2^(n/2))
Match
hash / binary search

The code

# does any subset of a sum to the target? O(2^(n/2)) def subset_sums(items): sums = [0] for x in items: sums += [s + x for s in sums] # double each item return sums def can_hit(a, target): mid = len(a) // 2 left = subset_sums(a[:mid]) right = set(subset_sums(a[mid:])) # hash for O(1) lookup return any((target - s) in right for s in left)

The same idea generalizes: 4-sum becomes two 2-sums, some knapsack variants split this way, and password/hash search meets from both ends. The rule of thumb — reach for meet-in-the-middle when a problem is 2ⁿ but n ≤ ~40 and the search splits into two combinable halves.

Quick check

1. Why is meet-in-the-middle O(2^(n/2)) and not O(2ⁿ)?

2. When is meet-in-the-middle the right tool?

FAQ

What is meet in the middle?

A technique that splits an exponential search into two halves, solves each, and combines them by matching partial results — turning 2ⁿ work into about 2·2^(n/2).

How does it solve subset-sum?

Enumerate the subset sums of each half, store one half in a hash set, and for each sum in the other half check whether target minus it exists in the set.

How big can n be?

Comfortably up to about 40, where 2^(n/2) ≈ 10⁶ is fast but 2^40 ≈ 10¹² is not. Beyond that, even the half is too large.

What else uses it?

4-sum (two 2-sums), partition problems, some knapsack variants, and cryptographic/hash search that meets from both ends.

Keep going

Algorithm

0/1 Knapsack →
Algorithm

Subsets & Backtracking →
Challenge

Two Sum →
Roadmap

The DSA Roadmap →
Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →