프로그래머스 43165 C++ DFS [타겟 넘버]

#include <bits/stdc++.h>
using namespace std;

int dfs(vector<int> &numbers, int target, int idx, int cur_sum) {
    if (idx == numbers.size()) {  // 끝까지 탐색한 경우
        if (cur_sum == target) {  // 누적합이 target과 일치하면 카운트(1 반환)
            return 1;
        }
        return 0;  // 일치하지 않으면 카운트 X
    }
    int cnt = 0;

    // 현재 깊이(인덱스)에서의 숫자를 더하는 경우
    cnt += dfs(numbers, target, idx + 1, cur_sum + numbers[idx]);

    // 현재 깊이(인덱스)에서의 숫자를 빼는 경우
    cnt += dfs(numbers, target, idx + 1, cur_sum - numbers[idx]);
    return cnt;
}

int solution(vector<int> numbers, int target) {
    int answer = dfs(numbers, target, 0, 0);
    return answer;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // example
    cout << solution({1, 1, 1, 1, 1}, 3) << '\n';
    return 0;
}