Meet In The Middle

Meet In The Middle

Tutorial

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})$

Copy
#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]; }

Copy
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