BOJ 1182번 :: 부분수열의 합

#문제

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

1182번: 부분수열의 합

 

#작성 코드

#include <iostream>
using namespace std;
 
int n, s, num[20], cnt=0;
 
void partsum(int idx, int sum){
    if( idx>=n ) return;
    int tmp = sum + num[idx];
    if( tmp == s ) cnt++;
    partsum(idx+1, sum);        // num[idx]를 포함하지 않는 경우 
    partsum(idx+1, tmp);        // num[idx]를 포함하는 경우 
}
 
int main(){
    // input 
    cin>>n>>s;
    for(int i=0; i<n; i++){
        cin>>num[i];
    }
    
    // solve
    // 1. 원소가 1개 ~ n개인 부분집합을 구한다.
    // 2. 그 부분집합의 원소의 합이 s이면 cnt를 1 증가시킨다.
    partsum(0, 0);
    
    // 3. cnt를 출력한다.
    cout<<cnt<<'\n';
    return 0;
}

#include <iostream>
using namespace std;
 
int n, s, cnt=0;
int nums[20];
 
int main(){
    cin>>n>>s;
    for(int i=0; i<n; i++){
        cin>>nums[i];
    }
    
    for(int bi=1; bi<(1<<n); bi++){
        int sum=0;
        // n이 5, bi가 10010이라면 우측에서부터 2번째, 5번째 인덱스 값을 포함한다는 뜻.
        // bi는 1 ~ 2^5 -1 이므로
        // bi의 개수는 원소가 5개인 집합의 부분집합 중 공집합을 제외한 개수가 된다. 
        for(int digit=0; digit<n; digit++){
            if( bi&(1<<digit) ){
                sum = sum+nums[digit];
            }
        }
        if( sum==s ) cnt++; 
    }
    
    cout<<cnt<<'\n';
    return 0;
}

##

1. 재귀를 이용한 방법

2. 비트마스킹을 이용한 방법