BOJ_1208 : 부분수열의 합 2

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40,

S

≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

C++ 코드

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

using namespace std;

int main() {
	int n, s;
	cin >> n >> s;
	vector<int> a(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int m = n / 2; // 중점
	 n = n - m;
	vector<int> first;
	vector<int> second;
	// 배열을 2분할
	// 두개의 배열에서 모든 부분집합을 구함
	for (int i = 0; i < (1 << m); i++) {
		int sum = 0;
		for (int j = 0; j < m; j++) {
			if (i & (1 << j)) {
				sum += a[j + n] ;
			}
		}
		second.push_back(sum);
	}

	for (int i = 0; i < (1 << n); i++) {
		int sum = 0;
		for (int j = 0; j < n; j++) {
			if (i & (1 << j  )) {
				sum += a[j];
			}
		}
		first.push_back(sum);
	}
	

	// 각각 반대로 정렬
	sort(first.begin(), first.end());
	sort(second.begin(), second.end(), greater<int>());

	n = (1 << n);
	m = (1 << m);
	int i = 0;
	int j = 0;
	long long ans = 0;
	while (i < n && j < m) {
		// 찾는값이 나온다면
		if (first[i] + second[j] == s) {
			i++;
			j++;
			long long c1 = 1;
			long long c2 = 1;
			// 연속적인 값을 체크함
			while (i < n && first[i] == first[i - 1]) {				
					c1++;
					i++;				
			}
			while (j < m && second[j] == second[j - 1]) {
					c2++;
					j++;
			}
			// first 에 2 가 두개 있고 
			// second 에 2가 두개 있고
			// 찾는 값 s == 0 이라면
			// 2 * 2  = 4 개의 부분집합이 가능하다.
			ans += c1 * c2;
		}
		else if (first[i] + second[j] < s) {
			i++;
		}
		else{
			j++;
		}

	}
	if (s == 0) ans--; 
	// 맨처음 0 + 0 값 제거
	cout << ans << '\n';
	return 0;
}