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

#include <iostream>
#include <unordered_map>
 
int N = 0;
int S = 0;
int arr[41] = {};
std::unordered_map<int, int> subsum = {};
long long count = 0;
 
void rightSum(int mid, int sum) 
{
    if (mid == N)
    {
        ++subsum[sum];
        return;
    }
 
    rightSum(mid + 1, sum + arr[mid]);
    rightSum(mid + 1, sum);
}
 
void leftSum(int left, int sum) 
{
    if (left == N / 2)
    {
        count += subsum[S - sum];
        return;
    }
 
    leftSum(left + 1, sum + arr[left]);
    leftSum(left + 1, sum);
}
 
int main() 
{
    std::cin >> N >> S;
 
    for (int i = 0; i < N; ++i) 
    {
        std::cin >> arr[i];
    }
 
    rightSum(N / 2, 0);
    leftSum(0, 0);
 
    if (!S) 
        std::cout << count - 1;
 
    else 
        std::cout << count;
 
    return 0;
}

 

모든 것들을 다 합산할 경우 2의 40승으로 무조건 시간 초과입니다.

2의 20승을 반으로 나눠서 계산하고 왼쪽합과 오른쪽합이

S가 될 수 있도록 합이 (오른쪽합)sum + S - (왼쪽합)sum이면 됩니다.