[백준 알고리즘] 1208번 부분 수열의 합2 문제풀이 c++

반으로 나누지 않으면 시간 초과가 된다.

 

수열을 반으로 나눠 계산한다.

왼쪽의 경우 가능한 모든 부분 수열의 합을 key로 하여 map에 개수를 저장한다.

오른쪽의 경우 가능한 모든 부분 수열의 합을 s에서 뺀 경우 map에 해당 key가 있다면

결과에 해당 개수를 더한다.

공집합인 경우에도 포함하여 계산되었으므로, s가 0이라면 res를 1감소시킨다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

vector<int> list;
int n,s;
long long res;
map<int, int> m;

void right(int pos, int sum){
	 if(pos == n){
	 	m[sum] ++;
	 }
	 else{
	 	right(pos+1, sum);
		right(pos+1, sum+list[pos]);
	 }
}
void left(int pos, int sum){
	if(pos==n/2){
		res += m[s-sum];
	}
	else{
		left(pos+1, sum);
		left(pos+1, sum+list[pos]);
	}
}
int main(){

	cin >> n >> s;

	int x;
	for(int i=0; i<n; i++){
	 	cin >> x;
		list.push_back(x);
	}
	right(n/2, 0);
	left(0, 0);
	
	if(s == 0)
		res --;
	cout << res;

	return 0;
}