Splitting an exponential search
When a problem needs you to consider all subsets of a set, the count of subsets doubles with each item. Meet in the middle cuts the exponent in half by splitting the set into two halves, enumerating all subsets of each half separately, then combining the two lists. The combined cost is roughly the square root of the brute force cost.
How combining works
Consider the classic subset sum question: is there a subset reaching a target sum.
- Enumerate every subset sum of the first half and store the values, often sorted.
- Enumerate every subset sum of the second half.
- For each second half sum, look for a first half sum that completes the target, using binary search or a hash set.
Because each half has only half the items, each list is far smaller than the full enumeration, and the lookup across them is cheap.
When it applies
Meet in the middle shines when the full set is too big for brute force but each half is manageable, and when partial results from the two halves can be combined by matching rather than nested iteration.
Key idea
Split the set, enumerate each half independently, and match the two result lists, reducing brute force exponential work to roughly its square root.