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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

풀이

💡 DFS, 재귀함수

• 종료 조건: numbers 배열의 모든 수를 선택 완료
• 다음 인덱스로 넘어가면서 + 또는 - 를 선택하여 연산한 값을 넘긴다. 

코드

#include <iostream>
#include <vector>

using namespace std;

int answer;

void dfs(int idx, int sum, int target, vector<int> &numbers) {
    if (idx == numbers.size()) {   // 종료 조건: 모든 수 탐색 완료
        if (sum == target) {    // target과 같으면 경우의 수 + 1
            answer++;
        }
        return;
    }

    dfs(idx + 1, sum + numbers[idx], target, numbers);  // + 선택
    dfs(idx + 1, sum - numbers[idx], target, numbers);  // - 선택
}

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

    dfs(0, 0, target, numbers);

    return answer;
}