Meet in the middle (sometimes called split and merge) is a clever idea that uses caching to get 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.

Let's go through a few applications.

Before we go on I want to mention that the additional problems are the best part of the article. Now let's go through a few applications of the trick.

h2. 4sum (popular interview question)

!blog/meet-in-the-middle?8puzzle.png!
# *4 reversals* We are given two equal length strings S and T. Figure out if we can get string T starting from string S and applying 4 substring reversal operations. (Hint: complexity O(n^5^))

The additional problems are the best part of the article so try to solve them in the comment section.

Try to solve them in the comment section.