[BOJ 1182] 부분집합의 합

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

n의 범위가 작으므로 그냥 재귀를 통한 완전탐색을 활용한다. 

이때 s==0일때는 공집합이므로 예외처리를 해주어야 한다. 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 1e18
typedef long long  ll;
using namespace std;
 
int n,s,arr[44],ans;
 
void solve(int cur , int sum){
    if(cur == n+1){ // 해당 범위를 벗어날때
        if(sum == s){
            ans ++;
        }
        return;
    }
    solve(cur+1,sum);
    solve(cur+1,sum+arr[cur]);
}
 
int main(){
    ans = 0;
    cin >> n >>s;
    for(int i=1;i<=n;i++){
        cin >> arr[i];
    }
    solve(1,0);
    if(s == 0){
        ans--;
    }
    cout << ans <<endl;
}