# Meet In The Middle

Author: Chongtian Ma

Divide the search space into two

## Meet In The Middle

Focus Problem – try your best to solve this problem before continuing!

### Tutorial

Resources | ||||
---|---|---|---|---|

CPH | ||||

Errichto |

### Pro Tip

Meet in the Middle technique can take advantage of the smaller constraint and calculate a naive solution in two halves. Therefore the constraints tend to be doubled.

### Naive Solution

Loop through all subsets in the array and if the sum is equal to $x$, then increase our answer. Worst case this does about $2^{40}$ operations, which is way too slow.

### Meet in the Middle Solution

We can divide the given array into two separate arrays. Let's say that the $\texttt{left}$ array runs from indexes $0$ to $\frac{n}{2}-1$, and the $\texttt{right}$ array runs from indexes $\frac{n}{2}$ to $n-1$. Both arrays will have at most $20$ elements, so we can loop through all subsets of these two arrays in at most $2^{21}$ operations, which is perfectly fine.

Now that we've got the subset sums of these two separate arrays, we need to recombine them to search for our answer. For every $\texttt{sum}$ in the $\texttt{left}$, we can simply check how many elements of $x - \texttt{sum}$ there are in $\texttt{right}$. This can be done using simple binary search.

Implementation

### Problems

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CF | Easy | ## Show TagsBinary Search, Meet in the Middle | |||

Silver | Easy | ## Show Tags2P, Meet in the Middle | |||

CF | Easy | ## Show TagsBinary Search, DFS, Meet in the Middle | |||

PrepBytes | Normal | ## Show TagsDP, Meet in the Middle | |||

YS | Normal | ## Show TagsBitmasks, DP, Meet in the Middle | |||

CF | Hard | ## Show TagsDFS, Meet in the Middle, NT | |||

CF | Hard | ## Show TagsBinary Search, DFS, Meet in the Middle |

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!