[C++] 백준 1182 부분수열의 합

https://www.acmicpc.net/problem/1182
제목 : 부분수열의 합
solved.ac 난이도 : Silver II

풀이

N개의 수열 내에서 합이 S인 부분수열을 찾는 과정은
문제에서 연속된 수열이라고 하지 않았기 때문에
순서를 고려하지 않는 부분집합의 합이 S인 경우를 찾는 과정과 동일하다고 볼 수 있다.

저는 부분집합을 구할 때 비트를 이용해 구했다.
예를 들어 2개의 원소가 있다고 가정을 하면 2개의 원소에 대한 부분집합은
{0 0}, {0 1}, {1 0}, {1 1} 4종류가 나온다
0부터 2진수를 1씩 더해가며 나오는 값이랑 동일하다고 볼 수 있다.
그러므로 우리는 비트 연산을 통해 부분집합을 구할 수 있다.

1부터 (1 << N) - 1 까지의 2진수의 값 들이 우리가 구하고자 하는 부분집합의 종류이고, 여기서 1부터 왼쪽으로 한칸씩 시프트 해가며
& 연산이 참일 경우에 해당 인덱스의 값을 더하고, 최종적으로 나온 부분집합의 합과 S가 동일하면 카운트 하는 식으로 해결했다.

#include <iostream>
#include <vector>

using namespace std;

void getcount(vector<int> &seq, int &S, int &count) {
    
    for (int i = 1; i < (1 << seq.size()); i++) {
        int sum = 0;
        for (int j = 1; j <= seq.size(); j++) {
            if (i & (1 << j - 1)) {
                sum += seq[j-1];
            }
        }
        if (sum == S) count++;
    }
}

int main()
{
    int N, S, num, count = 0;
    cin >> N >> S;
    vector<int> seq;
    for (int i = 0; i < N; i++) {
        cin >> num;
        seq.push_back(num);
    }
    getcount(seq, S, count);
    cout << count;
}