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

문제 설명

문제 링크

http://icpc.me/1208

1208번: 부분수열의 합 2

풀이

모든 조합을 뽑아서 확인해보면 O(2^40)이기 때문에 시간이 터진다.

그렇기 때문에 반절로 나눠서 모든 조합을 확인해봐야 한다.

x + y = s를 이용하여 오른쪽 조합에서 하나를 뽑아 s - y가 왼쪽 조합에 몇 개 존재하는지 이분 탐색을 이용하여 확인하면 모든 경우를 확인할 수 있다.

이때 몇 개가 존재하는지 확인할 때 upper_bound - lower_bound를 하면 구할 수 있다.

s가 0일 경우엔 왼쪽에서 아무것도 뽑지 않은 경우와 오른쪽도 아무것도 뽑지 않은 경우가 나올 수 있기 때문에 정답에 1을 뺀다.

코드

#include <bits/stdc++.h>
using namespace std;

int arr[42];
vector<int> a, b;

void dfs(int idx, int end, int sum, vector<int> &v) {
    if (idx == end) {
        v.push_back(sum);
        return;
    }
    dfs(idx + 1, end, sum + arr[idx], v);
    dfs(idx + 1, end, sum, v);
}

int main() {
    int n, s; scanf("%d %d", &n, &s);
    for (int i = 0; i < n; i++) scanf("%d", arr + i);
    int mid = n / 2;
    dfs(0, mid + 1, 0, a);
    dfs(mid + 1, n, 0, b);    
    sort(a.begin(), a.end());
    long long ans = 0;
    for (auto k : b) {
        auto u = upper_bound(a.begin(), a.end(), s - k);
        auto l = lower_bound(a.begin(), a.end(), s - k);
        ans += u - l;
    }
    if (!s) ans--;
    printf("%lld", ans);
}