[Programmers] 타겟 넘버

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

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

 

 

dfs로 풀었습니다.

 

이 문제는 이진트리의 구조를 이해하는 것이 중요합니다.

 

모든 경우를 더했을 경우 + 뺐을 경우의 수를 재귀로 구현했습니다.

 

#include <string>
#include <vector>

using namespace std;

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

int solution(vector<int> numbers, int target) {

    dfs(numbers, target, 0, 0);
    
    return answer;
}