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

백준 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;
}

• 두 배열의 부분 집합은 각각 공집합을 포함한다
  -> 때문에 s=0일 경우 답이 하나 더 크게 나온다
  -> if (s == 0) cnt--;

투 포인터 알고리즘 이용 풀이

• 공부할 예정

📌참고자료

• 백준 1208 부분수열의 합 2 풀이 (meet in the middle)
  https://justicehui.github.io/ps/2019/03/24/BOJ1208/

• 백준 1208 부분수열의 합 2 풀이 (투 포인터)
  https://jaimemin.tistory.com/1107