1208번 부분 수열의 합2

비트마스킹과 '중간에서 만나기'를 활용하였다.
'중간에서 만나기'란 양쪽 절반에서 모든 경우를 다 해보는 방법이다.
A에서 B까지 가는 시간이 60분이라고 할때, A -> C <- B 처럼 중간에서 만나면 30분만에 만날 수 있다.
이렇게 시간 복잡도가 2^N => 2^M + 2^M 으로 줄어든다.(이때 M = N/2)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	//freopen("in1.txt", "rt", stdin);
	int n, m, s;
	cin >> n >> s;
	vector<int> a(n + 1);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	m = n / 2;
	n = n - m;
	vector<int> first(1 << n);
	vector<int> second(1 << m);
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < n; j++) {
			if (i & (1 << j)) first[i] += a[j];
		}
	}
	for (int i = 0; i < (1 << m); i++) {
		for (int j = 0; j < m; j++) {
			if (i & (1 << j)) second[i] += a[j + n];
		}
	}
	sort(first.begin(), first.end());
	sort(second.begin(), second.end());
	reverse(second.begin(), second.end());
	n = (1 << n);
	m = (1 << m);
	int i = 0;
	int j = 0;
	long long cnt = 0;
	while (i < n && j < m) {
		if (first[i] + second[j] == s) {
			long long c1 = 1;
			long long c2 = 1;
			i++;
			j++;
			while (i < n && first[i] == first[i - 1])
			{
				c1++;
				i++;
			}
			while (j < m && second[j] == second[j - 1]) {
				c2++;
				j++;
			}
			cnt += c1 * c2;
		}
		else if (first[i] + second[j] > s) {
			j++;
		}
		else {
			i++;
		}
	}
	if (s == 0) cnt--;
	cout << cnt << '\n';
	return 0;
}