Meet-in-the-middle
Meet-in-the-middle - a way to optimize solutions, which consists in breaking the original problem into two halves, solving each independently, and then obtaining a solution to the original problem by combining the solutions of the halves.
Accordingly, it makes sense to use
meet-in-the-middle if two conditions are met.
1) The time required to solve half of the problem is asymptotically less than the time to solve the whole problem.
2) By solving half-problems, one can obtain solutions to the original whole problem and, at the same time, asymptotically faster than just solving the whole problem.
Example
Let there be four arrays of integers
A,
B,
C and
D. It is necessary to select exactly one number from each array so that the sum of these numbers is equal to zero. You can use a naive solution, namely, simply enumerate all possible options. This will work for
O(n4).
However, we can use
meet-in-the-middle.
Note that
a + b + c + d = 0 is equivalent to
(a + b) = -(c + d).
Let's divide the task into two halves, namely, in the first half we will use only arrays
A and
B, and in the second half only
C and
D.
Let's iterate over all the possible
(a + b) options in the first half and store all the values in a hash table (
unordered_map,
HashMap or the like. ). This works in
O(n2).
Now we will iterate over all possible options
(c + d) in the second half. When considering a certain option, we will check if there is a value in the hash table associated with the current sum of the opposite sign (then we found two reciprocals that add up to zero). This part also works in
O(n2).
We don't have a separate "
answer merge" phase here; in one, we did this in the course of solving for each of the halves. Most tasks will have a similar situation.
We ended up with a solution in
O(n2) using
meet-in-the-middle.
It is worth noting that
meet-in-the-middle is most often used when optimizing exponential solutions, which significantly affects the running time.