[C++] 프로그래머스 타켓넘버(DFS)

1. 문제

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

프로그래머스

 

2. 문제 해석

이 문제는 주어진 숫자를 적절히 더하거나 빼서 target를 맞추는 경우의 수를 구하는 문제이다. 예를 들어, [1, 1, 1, 1, 1] 이라는 배열이 주어졌을 때, 각각을 더하거나 뺄 수 있으므로 자연스럽게 트리 구조를 떠올릴 수 있다. 그래서 재귀적인 방법을 사용해 트리를 순회해 최종 리프 노드의 값이 target과 같으면 answer++ 해주면 된다.

 

#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++;
        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;
}