백준 1182번 (부분 수열의 합) c++

dfs로 중복하지 않는 부분수열 구함

 

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <deque>

using namespace std;

const int MAX = 20;
int N, S;
vector<int> v;
int re = 0;
int arr[MAX] = {0, };

void dfs(int num, int k, int m){
   if(k==m) { // M까지 들어갔을 시 실행
        int sum = 0;
        for(auto i =0;i<m;i++){
            sum += arr[i];
        }
        if(sum==S)re++;
    } else { // M까지 안 들어갔을 시
        for(auto i=num; i<N;i++) {
            arr[k]=v[i]; // 값 저장
            dfs(i+1,k+1, m); // 더 깊게
        }
    }
}

int main(){
    

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N>>S;
    for(int i=0;i<N;i++){
        int a;
        cin>>a;
        v.push_back(a);
    }
    for(int i=1;i<=N;i++){
        dfs(0,0,i);
    }
    cout<<re;

    
    
    return 0;
}