깊이 우선 탐색(DFS) // 프로그래머스 타겟넘버

#include <string>
#include <vector>
#include<iostream>
using namespace std;
void dfs(int start, vector<int> &temp, int target, int &answer){
   
    if(start<temp.size()){
        for(int i=0; i<2; i++){
            temp[start]=-1*temp[start];
            dfs(start+1,temp,target,answer);
        }
    }else{
        int temp2=0;
        for(int k=0; k<temp.size(); k++){
            temp2+=temp[k];
        }
        if(temp2==target){
            answer++;
        }
    }
}
int solution(vector<int> numbers, int target) {
    int answer = 0;
    dfs(0,numbers,target,answer);
    return answer;
}

// 깊이 우선 탐색인데 노드 끝까지 탐색을 안하고 target이랑 비교했었다.

말단 노드까지 탐색을 하고 거기서 모든 값을 더해 target이랑 비교해야됨 !