부분집합의 합 (비트마스크 전탐색)

### 문제 $N$개의 정수 $A_0, A_1, \ldots, A_{N-1}$이 주어진다. 이 중에서 **0개 이상**을 골라 만든 부분집합 중 합이 정확히 $K$인 것이 있는지 답하라. 공집합 (아무것도 안 고름)의 합은 $0$으로 본다. 따라서 $K = 0$이면 공집합이 답이 된다. ### 비트마스크 전탐색 $N$개의 원소가 있을 때 부분집합은 $2^N$개이다. 각 부분집합을 **$N$비트 정수** $\text{mask}$로 표현하자. $\text{mask}$의 $i$번째 비트가 1이면 "$i$번 원소를 골랐다"는 뜻이다. ```c for (int mask = 0; mask < (1 << N); mask++) { long long sum = 0; for (int i = 0; i < N; i++) { if (mask & (1 << i)) sum += A[i]; } if (sum == K) { ans = 1; break; } } ``` 총 시간 복잡도는 $O(N \cdot 2^N)$. $N \le 20$이면 $2^{20} \cdot 20 \approx 2 \times 10^7$이라 1초 안.