[백준/c++] 1182번: 부분수열의 합

문제 링크 - https://www.acmicpc.net/problem/1182

🌱 문제

![]

🌱 풀이

• 부분수열의 갯수는 2^n-1개이다. (공집합 제외)
• for문은 1부터 2^n-1 까지 돌린다.
• k값은 현재 i의 이진수값의 인덱스에 해당하는 변수이다. 원소 갯수는 N개 이므로 N번 반복하면 되고, (1<<K)는 이진수 'i의 끝에서 K번째 수'가 1인지 0인지 확인하는 연산이다.
  ex) 예를들어, i=15(1111), k=3이면 i 맨앞 자리(끝에서 0,1,2,3번째)수가 1인지 확인한다. i15&(1<<3) = 1 이므로 sum+=arr[3];
• 현재 값인 i와 (1<<k)의 AND연산을 통해 true일때만 arr[k]에 해당하는 수를 sum에 더하고, N번 다 돌면 sum이 s인지 확인한다.
• 각 i값과 (1<<k)

🌱 코드

//1182번: 부분수열의 합

/* 

N,S
1 <= N <= 20
|S| <= 1,000,000
합이 s가 되는 부분수열의 갯수 출력

 */

#include <iostream>
#include <cmath>
using namespace std;

int n,s;
int arr[21];
int cnt;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>s;
    int total= pow(2,n);

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

    for(int i=1; i<total ; i++){
        int sum=0;
        for(int k=0; k<n; k++){
            if(i&(1<<k)){
            sum+=arr[k];
            }
        }

        if(sum==s){
            // cout<<"i : "<<i<<"\n";
            cnt++;
        }
    }

    cout<<cnt<<"\n";
}