1208번: 부분수열의 합2

상당히 어려웠던 문제다.

1182 부분수열의 합에서 확장된 버전인데 속도가 관건이다.

개수의 범위가 40까지이므로 한번의 재귀 호출로는 해결이 불가능해보인다.

나는 입력 받은 배열을 앞과 뒤, 둘로 나눠 계산을 진행했다.

(int형으로는 모든 케이스를 커버하지 못한다)

#include <iostream>
#include <vector>
#include <algorithm>
 
 
int len, result;
std::vector<int> val;
std::vector<long long> frontSeq;
std::vector<long long> endSeq;
 
 
void DFS(int cur, long long sum, int limit) {
    if (cur == limit) {
        if (limit == len / 2) {
            frontSeq.push_back(sum);
        }
        else if (limit == len) {
            endSeq.push_back(sum);
        }
        return;
    }
 
    DFS(cur + 1, sum + val[cur], limit);
    DFS(cur + 1, sum, limit);
}
 
 
int main(void) {
    std::cin >> len >> result;
 
    int tmp;
    for (int i = 0; i < len; i++) {
        std::cin >> tmp;
        val.push_back(tmp);
    }
 
    DFS(0, 0, len / 2);
    DFS(len / 2, 0, len);
 
    std::sort(frontSeq.begin(), frontSeq.end());
    std::sort(endSeq.begin(), endSeq.end());
 
    long long count = 0;
    long long front = 0, end = endSeq.size() - 1;
    while (front < frontSeq.size() && end >= 0) {
        if (frontSeq[front] + endSeq[end] == result) {
            front++, end--;
            long long fCnt = 1, eCnt = 1;
            while (front < frontSeq.size() && frontSeq[front] == frontSeq[front - 1]) {
                front++;
                fCnt++;
            }
            while (end >= 0 && end < endSeq.size() && endSeq[end] == endSeq[end + 1]) {
                end--;
                eCnt++;
            }
            count += fCnt * eCnt;
        }
        else if (frontSeq[front] + endSeq[end] < result) {
            front++;
        }
        else if (frontSeq[front] + endSeq[end] > result) {
            end--;
        }
    }
    
    if (result == 0) {
        count--;
    }
    std::cout << count << "\n";
    return 0;
}