[B1182] - 부분집합의 합

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

부분수열의 합 문제입니다. N제한이 20으로

모든 경우를 해볼 수 있네요.

각각의 원소를 사용하는 경우와 사용하지 않는 경우로 나누어 비트마스크를 활용할 수 있는 문제입니다.

N제한이 커지면 비트마스크는 쓰기 어렵습니다.

i= 0은 어떤 원소도 선택하지 않은 공집합이기 때문에 진행하지 않습니다.

#include <iostream>
using namespace std;
int main()
{
    int n, s;
    cin >> n >> s;
    int a[20];
    int sum;
    int ans = 0;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 1; i < (1 << n); i++)
    {
        sum = 0;
        for (int j = 0; j < n; j++) {
            if (i&(1<<j))
            {
                sum += a[j];
            }
        }
        if (sum == s)
            ans++;
    }
    cout << ans << '\n';
}