1208번_부분집합의 합 2_BOJ

문제 링크

1208번 부분집합의 합 2 : https://www.acmicpc.net/problem/1208

문제 설명 및 해결 아이디어

정수의 개수 N이 범위가 1이상 40이하이므로, 부분집합의 개수는 2^40이 되기때문에 완전탐색으로 해결할 수 없다.

그래서 주어진 정수를 절반으로 나누어 왼쪽 절반과 오른쪽 절반의 모든 경우의 수를 구하는 방법으로 접근해야한다.

그래서 O(2^(N/2)log2^(N/2))으로 해결할 수 있다.

부분집합을 구하는 방법은 아래의 코드를 참고하면 된다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long int
#define MAX_S 41
 
int n, s;
int a[MAX_S], b[MAX_S];
vector<int> asum, bsum;
 
int main() {
    scanf("%d %d", &n, &s);
    int alen = n / 2;
    int blen = n - alen;
 
    for (int i = 0; i < alen; ++i)
        scanf("%d", &a[i]);
    for (int i = 0; i < blen; ++i)
        scanf("%d", &b[i]);
 
    for (int i = 0; i < (1 << alen); ++i) {
        int sum = 0;
        for (int j = 0; j < alen; ++j) {
            if (i&(1 << j))
                sum += a[j];
        }
        asum.push_back(sum);
    }
 
    for (int i = 0; i < (1 << blen); ++i) {
        int sum = 0;
        for (int j = 0; j < blen; ++j) {
            if (i&(1 << j))
                sum += b[j];
        }
        bsum.push_back(sum);
    }
 
    sort(asum.begin(), asum.end());
    sort(bsum.begin(), bsum.end());
 
    ll ans = 0;
    ll res, lo, hi;
    for (int i = 0; i < bsum.size(); ++i) {
        res = s - bsum[i];
        lo = lower_bound(asum.begin(), asum.end(), res) - asum.begin();
        hi = upper_bound(asum.begin(), asum.end(), res) - asum.begin();
        ans += hi - lo;
    }
 
    if (s == 0)
        ans--;
    printf("%lld\n", ans);
    return 0;
}