[CodeUp] #3009-부분수열의 합(탐색기반설계)

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

int cnt = 0;
vector<int> num;
void sum(int add,int s,vector<int> v,int index){
    if(add==s){
        int chk = 0;
        for(int i=0;i<v.size();i++){
            if(v[i]){
                chk++;
            }
        }

        /*for(int i=0;i<v.size();i++){
            if(v[i]){
                cout << num[i] << " ";
            }
        }
        cout << add << "\n";*/
        if(chk>0){
            cnt++;
        }
        
    }

    for(int i=index;i<num.size();i++){
        if(v[i]==0){
            v[i] = 1;
            sum(add+num[i],s,v,i+1);
            v[i] = 0;
        }
    }
    return;
}

int main(){
    int n,s;
    vector<int> v;
    cin >> n >> s;
    num.resize(n,0);
    v.resize(n,0);

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

    sum(0,s,v,0);

    cout << cnt;


}