[백준/BOJ] 1182번 부분수열의 합 (C++)

www.acmicpc.net/problem/1182

1182번: 부분수열의 합

브루트 포스(완전 탐색) 유형의 문제

현재 누적합과 현재 인덱스 값을 더한게 s와 같은지 확인해서 같으면 answer를 증가시키고, 그게 아니라면 현재 인덱스 값을 더하거나, 더하지 않고 그대로 재귀함수를 호출합니다. 이때 sum + v[idx]의 값과 s의 비교를 기저조건에서 하지 않는 이유는 입력값의 조건이 음수가 포함이므로 이를 기저조건에 두면 답인 경우가 더해지지 않는 경우가 발생하기 때문입니다.

 

#include <iostream>
#include <vector>
using namespace std;

int n, s, answer = 0;
vector<int> v;

void DFS(int idx, int sum) {
	if(idx == n) return;
    if(sum + v[idx] == s) answer++;
    
    DFS(idx + 1, sum + v[idx]);
    DFS(idx + 1, sum);
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>s;
    v.assign(n, 0);
    
    for(int i = 0; i < n; i++) {
        cin>>v[i];
    }
    
    DFS(0, 0);
    cout<<answer;
}