[BOJ] 1182. 부분수열의 합 (C++)

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수

생각할 것

종료 조건에 부분수열 원소 개수는 상관없고 더한 값만 필요하므로 방문 체크를 하지 않았다.

모든 조합을 확인해야한다. ⇒ 부분 수열을 만들때, 해당 원소가 들어가는지 안들어가는지 여부로 판단한다!

코드

#include <iostream>
#include <vector>

using namespace std;

int N, S, res = 0;
vector<int> num;

void dfs(int idx, int sum) {
    // 결괏값 확인
    if (idx == N) return; // 모든 수를 다 확인한 경우
    if (sum + num[idx] == S) res++; // 정답인지 확인

    // 아니면 다음 인덱스로 넘어감 (현재 숫자를 더하거나 안 더한 채로 넘어감)
    dfs(idx + 1, sum);
    dfs(idx + 1, sum + num[idx]);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> S;
    num.assign(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> num[i];
    }

    dfs(0, 0);
    cout << res;

    return 0;
}