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

정말 가장 기본적인 DFS문제이다.

각 원소는 + 혹은 -가 될 수 있고 모든 원소의 합이 target인지 확인하면 된다.

DFS로 정수들의 배열에서 더하고 빼고 가능한 모든 경우를 확인하여

target인 경우 answer을 증가하도록 구현하였다.

 

 

#include <string>
#include <vector>

using namespace std;

int answer =0;

void DFS(vector<int> &num, int &t, int depth, int sum){
    if(depth == num.size()){
        if(sum == t){
            answer++;
        }
    }
    else{
        DFS(num, t, depth+1, sum + num[depth]);
        DFS(num, t, depth+1, sum - num[depth]);
    }
}

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