Meet in the middle (sometimes called split and merge) is a clever approach which tries to trade off space for time. Much like divide et impera it divides the problem in two and then tries to merge the results. The benefit is that by using quite a bit of memory you can tackle problems of twice the size you could before.

Meet in the middle (sometimes called split and merge) is a clever idea that uses caching to get more efficient solutions. Much like divide et impera it divides the problem in two and then tries to merge the results. The benefit is that by using quite a bit of extra memory you can tackle problems of twice the size you could before.

Here are a few applications.

Let's go through a few applications.

h2. 4sum

A slightly improved algorithm brute forces through all $n^3^$ three number combinations and efficiently checks if -(a + b + c) is in the original array using a hash table. This algorithm has $O(n^3^)$ complexity.

By now, you’ve probably started thinking how the meet in the middle technique could be applied to this problem. The trick is to rewrite the equation as: $a + b = -(c + d)$. Store all the $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains -(c + d).

By now, you’ve probably started wondering how the meet in the middle technique could be applied here. The insight comes from rewriting $a + b + c + d = 0$ as $a + b = -(c + d)$.
Now we store all $n^2^$ sums $a + b$ in a hash set $S$. Then iterate through all $n^2^$ combinations for c and d and check if $S$ contains -(c + d).

Here's how the code looks