타겟 넘버

코드

#include <string>
#include <vector>

using namespace std;
int answer = 0;
void DFS(vector<int>& v, int sum, int target, int depth){
    if(depth == v.size()){
        if(sum == target) answer++;
        return;
    }else{
        DFS(v, sum+v[depth], target, depth+1);
        DFS(v, sum-v[depth], target, depth+1);
    }
}
int solution(vector<int> numbers, int target) {
    DFS(numbers, 0, target, 0);
    return answer;
}

• DFS는 stack으로 구현할 수도 있지만, 재귀로도 구현될 수 있음을 기억하자
• DFS의 원리는 깊게 하나의 경우의 수를 처리하는 것으로 생각할 수 있음