[algorithm] 백준 - 부분 수열의 합 2

brute force 문제이다.

 

정수의 개수는 40개이므로 2 ^ 40 번의 연산을 필요로 하니까 시간 제한 내에 풀기 위해 반으로 쪼개서 연산해야한다.

 

절반을 기준으로 leftDfs rightDfs로 나누어서 풀었다.

 

leftDfs의 경우,

부분 수열의 합의 개수를 저장하고,

 

rightDfs에서는,

구하고자 하는 합 - rightDfs에서 연산한 부분 수열의 합이 있는지 찾은 후

answer에 추가시키는 방식으로 풀었다.

 

그리고 구하고자 하는 합이 0일 경우,

leftDfs에서 부분 수열의 합에 포함되는 수가 없는 경우, rightDfs에서 부분 수열의 합에 포함되는 수가 없는 경우로

동일한 경우가 2번 연산되므로 한번 빼준다.

 

//부분 수열의 합2
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
map<long long,long long> numberMap;
vector<int> numberVector;
long long answer = 0; 
void leftDfs(int target, int index, long long sum){
    if(target == index){
        numberMap[sum]++;
        return;
    }
    leftDfs(target, index + 1, sum + numberVector[index]);
    leftDfs(target, index + 1, sum);
}
void rightDfs(int target, int index, long long sum, int baseNum){
    if(target == index){
        answer += numberMap[baseNum - sum];
        return;
    }
    rightDfs(target, index + 1, sum + numberVector[index], baseNum);
    rightDfs(target, index + 1, sum, baseNum);
}
int main(void){
    int count, baseNum, num;
    cin >> count >> baseNum;
    for(int i = 0; i < count; i++){
        cin >> num;
        numberVector.push_back(num);
    }
    leftDfs(count/2, 0, 0);
    rightDfs(count, count / 2, 0, baseNum);
    if(baseNum == 0) answer--;
    cout << answer;
}