[백준]부분수열의 합 - 복습

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

 

5개의 숫자중 1개 선택하는경우 + 2개 선택하는경우 + 3개 선택하는경우 ...
5C1 + 5C2.. 2^5

 

2^5까지의 값을 2진수로 생각해보면
각 자리수를 한번씩 토글한다

해당 자리수 토글을 해당 수열을 선택했다고 생각하자

 

#include <iostream>
#include <math.h>

using namespace std;

int input[21];

int main()
{
    int N, S;
    int cnt = 0;

    cin >> N >> S;

    for (int i = 0; i < N; i++)
    {
        cin >> input[i];
    }

    for (int i = 1; i < pow(2, N); i++)
    {
        int sum = 0;
        for (int j = 0; j < N; j++)
        {
            if (i & (1 << j)) {
                sum += input[j];
            }
        }
        if (sum == S)
            cnt++;
    }

    cout << cnt << endl;
}