부분수열의 합2 1208번 [백준]

오랜만에 백준 문제를 풀어 보았다. meet in the middle이라는 기법을 활용하여 푸는 문제이다.

meet in the middle이라는 기법을 처음 접해 보았는데, 부분수열의 합1에서 모든 경우의 수를 구하여 풀었던 것을 같이 활용하여 문제를 풀 수 있었다.

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(int i=0;i<j;i++)
#define mrep(i,j,k) for(int i = j; i<=k;i++)
#define drep(i,j,k) for(int i = j; i>=k; i--)
typedef long long ll;


int main() {
	//#ifndef ONLINE_JUDGE
	//    freopen("input.txt", "r", stdin);
	//#endif
	fast_io;
	int N, S;
	cin >> N >> S;
	vector<int> v(N);
	rep(i, N)cin >> v[i];
	int half = N / 2;
	vector<int> first(1 << (N - half));
	for (int i = 0; i < 1 << (N - half); i++) {//calculate all the case1
		for (int j = 0; j < N - half; j++) {
			if (i & (1 << j))first[i] += v[j];
		}
	}
	vector<int> second(1 << half);
	for (int i = 0; i < 1 << half; i++) {//calculate all the case2
		for (int j = 0; j < half; j++) {
			if (i & (1 << j))second[i] += v[j + (N - half)];
		}
	}
	ll result = 0;
	sort(first.begin(), first.end());
	sort(second.begin(), second.end(),greater<int>());
	ll idx = 0, idx2 = 0;
	while (idx < 1 << (N - half)&& idx2 < 1 << half) {//point to point algorithm
		if (first[idx] + second[idx2] == S) {
			ll cnt1 = 1, cnt2 = 1;
			idx++;
			idx2++;
			while (idx < 1 << (N - half) && first[idx] == first[idx - 1]) {
				idx++;
				cnt1++;
			}
			while (idx2 < 1 << half && second[idx2] == second[idx2 - 1]) {
				idx2++;
				cnt2++;
			}
			result += cnt1 * cnt2;
		}
		else if (first[idx] + second[idx2] > S) {
			idx2++;
		}
		else if (first[idx] + second[idx2] < S) {
			idx++;
		}
	}
	if (S == 0)result--;
	cout << result;
	return 0;
}

https://www.acmicpc.net/problem/1208