1182번 : 부분수열의 합 - junnnho

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

dfs를 통해 모든 수를 다 방문하면서 합이 같아지는 부분이 있는지 확인했다.

 

1개는 현재의 합에서 현재 방문한 수를 빼고 다음수를 확인하는 재귀,

1개는 현재의 합을 그대로 다음수를 확인하는 재귀

총 2개의 재귀를 이용하면 쉽게 해결된다.

 

#include <cstdio>
#include <vector>
using namespace std;
 
int N, S, check;
int arr[20];
 
void dfs(int start, int sum) {
    sum += arr[start];
 
    if (start >= N)
        return;
 
    if (sum == S) {
        check++;
    }
 
    dfs(start + 1, sum - arr[start]);
    dfs(start + 1, sum);
}
 
int main() {
    scanf("%d%d", &N, &S);
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    dfs(0,0);
    printf("%d", check);
}