[백준] 1208번 부분 수열의 합2 (C++)

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

처음에 1182번인 부분수열의 합 문제를 남들과 다른 방식으로 풀어서 헷갈렸던 문제였다.
다른 사람들의 풀이를 보며 충분히 이해하고 풀 수 있게 되었다.
처음에 N이 40까지라서 2^40은 1조를 넘기 때문에 단순하게 풀면 시간초과가 난다.
해서 N을 반으로 나눠준 뒤, 각자 부분 수열의 합을 구하면 된다.

0~n/2까지의 부분 수열의 합을 map 자료구조를 이용해 넣어준다.
n/2~n까지의 부분 수열의 합을 구할땐 map[S-sum] 형태를 이용해서 기존의 넣었던 값과의 합이 S가 되면 결과를 하나씩 더해준다.

이때, S가 0인 경우는 왼쪽, 오른쪽 배열이 모두 공집합일때가 있으므로 결과값에서 하나를 빼준다.

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

int num[41];
int n, s;
map<int, int> total;
long long ret = 0;

void leftSum(int st, int sum) {
	if (st == n / 2) {
		total[sum]++;
		return;
	}
	leftSum(st + 1, sum);
	leftSum(st + 1, sum + num[st]);
}

void rightSum(int m, int sum) {
	if (m == n) {
		ret += total[s - sum];
		return;
	}
	rightSum(m + 1, sum);
	rightSum(m + 1, sum + num[m]);
}

int main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(NULL);
	cin >> n >> s;
	for (int i = 0; i < n; i++)
		cin >> num[i];
	leftSum(0, 0);
	rightSum(n / 2, 0);
	if (s == 0)
		cout << ret - 1;
	else
		cout << ret;
}