프로그래머스 Level2 - 타겟 넘버 C++

코딩테스트 연습 - 타겟 넘버

#include <string>
#include <vector>

using namespace std;
int answer = 0;
void dfs(vector<int> numbers, int target, int i, int sum){
    int n = numbers.size();
    
    if(i >= n){
        if(sum == target)
            answer++;
        return;
    }
    // 0부터 시작을 했으니
    dfs(numbers, target, i+1, sum+numbers[i]);
    dfs(numbers, target, i+1, sum-numbers[i]);
    
}

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

---

 처음에는 큐를 이용한 bfs라고 착각했던 문제. 생각해보니 깊이로 뭔가를 얻는건 없고 트리를 끝까지 탐색해서 풀이하는게 목적이었다. 그래서 재귀를 이용한 DFS로 문제를 풀이했습니다.