1182번 부분수열의 합

 브루트포스 문제

 

 6603번 로또문제를 이용해 해결하였다.

 1. N개의 숫자 중 1개씩 선택할 경우를 구해 S의 값과 비교한다. 

 2. N개의 숫자 중 2개씩 선택할 경우를 구해 S의 값과 비교한다.

 3. 이런 방식으로 N개씩 선택할 경우까지 구하면 된다.

 

 

#include <iostream>
#include <vector>
#define MAX 21
 
using namespace std;
 
int N,S;
vector<int> vec;
int store[MAX];
int ans;
 
 
void solved(int num, int step, int cnt){
    
    if(cnt==num){
        int sum=0;
        for(int i=0;i<num;i++){
            sum+=store[i];
        }
        if(sum==S){
            ans++;
        }
        return;
    }
    else{
        for(int i=step;i<N;i++){
            store[cnt]=vec[i];
            solved(num, i+1, cnt+1);
        }
    }
}
 
int main(){
    cin >> N >> S;
    
    for(int i=0;i<N;i++){
        int num;
        cin >> num;
        vec.push_back(num);
    }
    
    for(int num=1;num<=N;num++){
        solved(num,0,0);
    }
 
    cout << ans << endl;
}