[백준] 1182번 부분수열의 합

 

[적용한 알고리즘]

재귀

[아이디어]

X

[생각의 흐름 / 절차] 

경우의 수가 2^n 개이고 n<20 이니까 일일이 다 해봐도 괜찮겠다.

 

[교훈]

재귀를 더 연습해보자

 

<코드>

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int arr[20];
int ans;
int n, goal;

void go(int index, int sum){
    if (index == n){
        if (sum == goal){
            ans++;
        }
        return;
    }
    go(index + 1, sum + arr[index]); //부분 수열에 포함시키는 경우
    go(index + 1, sum); // 부분 수열에 포함시키지 않는 경우
}

int main(){
    scanf("%d %d", &n, &goal);

    for (int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }

    go(0, 0);
    if (goal == 0){
        ans--;
    }

    printf("%d\n", ans);

    return 0;
}