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

🌽 문제

🥔 풀이

모든 경우의 수를 탐색해야 하므로 DFS로 풀어야 하는 문제.
nums의 모든 수를 다 사용하면: lev == nums.size()
누적합 sum이 target과 같은지 확인하여
경우의 수를 갱신하고 dfs 함수를 빠져나가길 반복한다.

🥬 코드

#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int> nums, int t, int lev, int sum) {
    if (lev == nums.size()) {
        if (sum == t) answer++;
        return;
    }
    dfs(nums, t, lev + 1, sum + nums[lev]);
    dfs(nums, t, lev + 1, sum - nums[lev]);
}

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

🥜 채점