프로그래머스 코테 연습 : 타겟 넘버 [C++] DFS

DFS의 정석과 같은 문제다. 

스택이 아닌 재귀로 문제를 해결했다.

이문제의 경우 각각의 경우에 따른 sum과 count를 알아야해서 sum과 count가 전역으로 선언되어서는 안된다. 

dfs 가 호출될때 sum, count를 같이 넘겨 주는 식으로 해야한다 각각의 dfs 경로별로 sum과 count 가 다르기 때문이다.

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int> numbers, int target, int sum, int count){
    if(count == numbers.size()){
        if(sum == target){
            answer++;
        }
        
        return;
    }
    // 합하고 다음걸로 넘어감
    dfs(numbers, target, sum + numbers[count], count+1);
    dfs(numbers, target, sum - numbers[count], count+1);
    
}

int solution(vector<int> numbers, int target) {
    
    // dfs를 호출할때마다 sum과 count를 알아야 하므로 파라미터에 포함시킨다.
    dfs(numbers, target, 0, 0);
    return answer;
}