Meet In The Middle

#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]; }
 
	// stores all possible subset sums in the interval [l, r]
	auto get_subset_sums = [&](int l, int r) -> vector<ll> {
		int len = r - l + 1;
		vector<ll> res;
 
		// loop through all subsets
		for (int i = 0; i < (1 << len); i++) {
			ll sum = 0;
			for (int j = 0; j < len; j++) {
				if (i & (1 << j)) { sum += a[l + j]; }
			}
			res.push_back(sum);
		}
 
		return res;
	};
 
	vector<ll> left = get_subset_sums(0, n / 2 - 1);
	vector<ll> right = get_subset_sums(n / 2, n - 1);
	sort(left.begin(), left.end());
	sort(right.begin(), right.end());
 
	ll ans = 0;
	for (ll i : left) {
		auto low_iterator = lower_bound(right.begin(), right.end(), x - i);
		auto high_iterator = upper_bound(right.begin(), right.end(), x - i);
		ans += high_iterator - low_iterator;
	}
 
	cout << ans << endl;
}

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(); }
 
		long[] left = get_subset_sums(a, 0, n / 2 - 1);
		long[] right = get_subset_sums(a, n / 2, n - 1);
		Arrays.sort(right);
 
		long answer = 0;
		for (long i : left) {
			int low_index = lower_bound(right, x - i);
			int high_index = lower_bound(right, x - i + 1);
			answer += high_index - low_index;
		}
 
		io.println(answer);
		io.close();
	}
 
	/*
	 * returns an array with all possible subset sums
	 * from [l..r]
	 */
	public static long[] get_subset_sums(int[] a, int l, int r) {
		int len = r - l + 1;
		int index = 0;
		long[] sums = new long[1 << len];
 
		for (int i = 0; i < (1 << len); i++) {
			for (int j = 0; j < len; j++) {
				if ((i & (1 << j)) != 0) { sums[index] += a[j + l]; }
			}
			index++;
		}
 
		return sums;
	}
 
	// finds the first index which has equal or greater than an element.
	public static int lower_bound(long[] arr, long x) {
		int l = -1, r = arr.length;
		while (l < r - 1) {
			int mid = l + (r - l) / 2;
			if (arr[mid] < x) {
				l = mid;
			} else r = mid;
		}
		return r;
	}
 
	// CodeSnip{Kattio}
}

import collections
 
n, x = map(int, input().split())
t = list(map(int, input().split()))
 
 
def get_subset_sums(l: int, r: int) -> collections.Counter:
	sums = [0]
	for ti in t[l:r]:
		sums.extend([s + ti for s in sums])
	return collections.Counter(sums)
 
 
# compute sum frequencies for first and second part of the array
freq = [get_subset_sums(0, n // 2), get_subset_sums(n // 2, n)]
 
# combine results of both parts
answer = 0
for s in freq[0]:
	answer += freq[0][s] * freq[1].get(x - s, 0)
 
print(answer)