Lesson 38.2 · Advanced Search and Divide & Conquer
Meet in the Middle
When n is around 40, 2ⁿ subsets are too many, but 2^(n/2) ≈ 10⁶ is fine. Enumerate each half separately, sort one side, and combine with binary search or a hash map.
14 min
Think of it like this
Two friends searching for each other in a city: if each walks halfway, they meet much sooner than if one waits and the other searches the whole city.
1.Split, enumerate, join
Split the items into halves A and B. List all subset sums of A and of B (2^(n/2) each). Sort B's sums. For each sum a in A, binary search B for the value closest to (target − a). Total O(2^(n/2) × n).
Variants: count pairs with a hash map (4Sum II splits four arrays into two pairs), or group sums by how many items they use when the split must be balanced (partitioning into two equal-size halves).
Quick check
n = 40: how many subset sums does each half produce?
Remember
- n ≈ 40 is the signal.
- Enumerate halves, sort one, search from the other.
- Hash maps when counting exact matches.
Common mistakes
- Storing subset sums in a HashSet when you need the closest value (needs sorting).