# Meet In The Middle

Author: Chongtian Ma

Problems involving dividing 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.

Time Complexity: $O(N\cdot 2^{N/2})$

C++

#include <bits/stdc++.h>using namespace std;using ll = long long;int main() {int n, x;cin >> n >> x;vector<int> a(n);for (int i = 0; i < n; i++) { cin >> a[i]; }

Java

### Warning: Tight Time Limit

CSES has very tight time constraints for java, so the following code will barely pass in around 1 second. It is not guaranteed to pass on first submits, so you might need to submit multiple times.

import java.io.*;import java.util.*;public class Main {public static void main(String[] args) {Kattio io = new Kattio();int n = io.nextInt(), x = io.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) { a[i] = io.nextInt(); }

### 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 | |||

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 | |||

Kattis | Hard | ## Show TagsDFS, Meet in the Middle, PIE |

### 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!