백준 부분수열의 합 (1182) 재귀로

부분 수열을 구할때 재귀 적으로 원소를 더해 주거나 더해주지 않거나 ..하면 모든 조합을 구할수 있다.

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

#include <stdio.h>
#include <iostream>
#include <memory.h>
 
using namespace std;
 
#define MAX(a,b) ((a) > (b)) ? ((a):(b))
#define MIN(a,b) ((a) > (b)) ? ((b):(a))
 
int in[21]; //입력값  
 
 
bool visited[20];
int N, S;
int ans = 0;
 
 
//recursive 재귀함수 ..구현 //
 
//idx, sum //
void recursive(int idx, int sum) {
 
    if (idx == N){
        
        if (sum == S)
            ans++; 
    }
    //입력값에 대해서 모두 더하는경우와 
    recursive(idx + 1, sum + in[idx]);
 
    //jump 즉 계산하지 않는 경우를 모두 고려한다
    recursive(idx + 1, sum);
 
}
 
int main(void){
 
    int TC = 1;
    //freopen("input.txt", "r", stdin);    setbuf(stdout, NULL);    
 
 
 
    ans = 0;
    cin >> N >> S;
 
    memset(visited, false, sizeof(visited));
 
 
    for (int i = 0; i < N; i++)
        cin >> in[i];
 
    recursive(0, 0);
 
    if (S == 0) // 0일경우 하나도 더하지 않은 경우도 count 되기 때문에 빼준다 
 
        ans--;
 
 
    cout << ans << endl;
 
    return 0;
}