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

⋆｡♡ﾟ☁︎ ⋆｡선주 ﾟ☁︎ ﾟ｡♡⋆｡·2022년 1월 15일

미해결 백준

백준

목록 보기

32/271

백준 1208 부분수열의 합 2

https://www.acmicpc.net/problem/745
전체 배열의 부분 집합의 합 = 배열을 두 개로 나누어 각각의 부분 집합의 합을 더하여 구한다

map container 이용 풀이

map<int, int> mp
-> mp[sum]: 합이 sum인 부분 집합의 개수 저장

#include <iostream>
#include <map>
using namespace std;

const int MAXN = 40;

int n, s;
long long cnt = 0;
int num[MAXN + 1]; 
map<int, int> mp;

void dfsLeft(int index, int sum) {
	if (index == n/2) {
		++mp[sum];
		return;
	}
	dfsLeft(index + 1, sum);
	dfsLeft(index + 1, sum + num[index]);
	return;
}

void dfsRight(int index, int sum) {
	if (index >= n) {
		cnt += mp[s-sum];
		return;
	}
	dfsRight(index + 1, sum);
	dfsRight(index + 1, sum + num[index]);
	return;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> s;
	for (int i = 0; i < n; ++i)
		cin >> num[i];

	dfsLeft(0, 0);
	dfsRight(n/2, 0);

	if (s == 0) cnt--;
	cout << cnt;
	return 0;
}