백준 1182번 부분수열의 합 소스 코드 - 비트마스크

1182번: 부분수열의 합 (acmicpc.net)

1182번: 부분수열의 합

 

[ 백준 1182번 부분수열의 합 소스코드 - 비트마스크 ]

#include <iostream>
using namespace std;
int a[20];
int main() {
    int n,s;
    cin >> n >> s;
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    //전체집합 = (1<< n)-1  공집합은 제외 
    for (int i=1; i<(1<<n); i++) {
        int sum = 0;
        for (int k=0; k<n; k++) {
            if ( i&(1<<k)) {
                sum += a[k];
            }
        }
        if (sum == s) {
            ans += 1;
        }
    }
    cout << ans << '\n';
    return 0;
}