1208 - 부분집합의 합 2

문제 링크

---

https://www.acmicpc.net/problem/1208

문제 요약

---

크기 \(N\)인 집합이 주어진다. 이 때 부분집합의 합이 \(S\)가 되는 경우의 수를 구하는 문제다.

문제 풀이

---

\(N\)이 최대 40이기 때문에 완전탐색으로는 안된다. 따라서 다른 방법이 필요하다. 이런 경우에는 왼쪽 절반과 오른쪽 절반의 모든 경우의 수를 각각 구하고 이분탐색을 통해 이 경우의 수를 합쳐나갈 수 있다.

크기 \(N\)인 집합을 왼쪽부터 \(N \above 1pt 2\)개의 완전탐색 경우의 나머지 오른쪽의 완전탐색 경우를 다 구해 놓는다. 이 때 왼쪽의 경우의 수와 오른쪽 경우의 수를 어떻게 합쳐야 할까? 왼쪽의 경우 중 가능한 한가지 합이 \(x\)라고 가정을 해 보자. 그렇다면 오른쪽 경우의 수에서 찾아야 할 합은 \(S-x\)가 될 것이다. 따라서 왼쪽의 경우의 수에 대해서 가능한 오른쪽의 모든 경우의 수를 찾아 답에 누적해 나가면 된다.

\(N\)이 40일 때 시간복잡도는 \(O(2^{20}log2^{20})\)이므로 시간내에 들어올 수 있다.

소스 코드

---

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int N, S, A[41];

void func(int pos, int end, int sum, vector<int>& vi) {
  if (pos == end) {
    vi.push_back(sum);
    return;
  }
  func(pos + 1, end, sum, vi);
  func(pos + 1, end, sum + A[pos], vi);
}

int main() {
  scanf("%d%d", &N, &S);
  for (int i = 0 ; i < N ; ++i) {
    scanf("%d", &A[i]);
  }
  vector<int> L, R;
  func(0, N / 2, 0, L);
  func(N / 2, N, 0, R);
  
  sort(R.begin(), R.end());
  long long ans = 0;
  for (int val : L) {
    int target = S - val;
    auto hi = upper_bound(R.begin(), R.end(), target);
    auto lo = lower_bound(R.begin(), R.end(), target);
    ans += hi - lo;
  }
  
  if (S == 0) {
    --ans;
  }
  printf("%lld\n", ans);
}