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

https://programmers.co.kr/learn/courses/30/lessons/43165 

프로그래머스

 

풀이 과정

dfs의 대표적인 문제인 것 같다.  
dfs문을 돌렸을 때 cnt값이 numbers.size()와 같고, target이 sum과 같다면  
타겟 넘버를 만들었다는 뜻이므로 답을카운트 해준다.

 

#include <string>
#include <vector>

using namespace std;

int res = 0;

void dfs(vector<int> numbers, int target, int sum, int cnt){
    if(cnt == numbers.size()){
        if(target == sum) res++;
        return;
    }
    dfs(numbers, target, sum + numbers[cnt], cnt + 1);
    dfs(numbers, target, sum - numbers[cnt], cnt + 1);
}

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