[BOJ] 1182 - 부분수열의 합

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

BOJ - 부분수열의 합

문제 유형: 브루트포스, 백트래킹, 비트마스킹

문제 난이도: Silver II

시간 제한: 2초

메모리 제한: 256MB

 

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

 

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

 

풀이

백트래킹 또는 비트마스킹으로 풀 수 있다.

백트래킹으로 집합에 넣을까말까를 정하거나, 비트마스킹으로 각 자릿수별로 수의 소속 표현을 하면서 합을 구해서 집합을 구성하고 비교하면 된다.

 

여기서는 비트마스킹으로 다룬다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n, s;
int arr[20];

int ans = 0;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n >> s;
  for (int i = 0; i < n; ++i) {
    cin >> arr[i];
  }

  int mask = (1 << n) - 1;
  for (int i = 1; i <= mask; ++i) {
    int sum = 0;
    for (int j = 0; j < n; ++j) {
      if (i & (1 << j))
        sum += arr[j];
    }
    if (sum == s)
      ans++;
  }

  cout << ans << "\n";

  return 0;
}