<Programmers> DFS/BFS_타겟 넘버 (Target Number) c++

테스트 케이스로 주어진 예를 보면
{1, 1, 1, 1, 1} 이 주어져 있을 때 이 숫자들을 +, -로 적당히 조합해서 Target Number가 되는 경우의 개수를 세는 것이다.

처음 수가 +1 인 경우와 -1인 경우로 나누어 생각하면
{ +1, a, b, c, d}, {-1, e, f, g, h} 로 나누어지고
여기서 각각 a와 e는 다시 +1과 -1로 나누어진다.
{+1, +1, b, c, d}, {+1, -1, b, c, d}
{-1, +1, f, g, h}, {-1, -1, f, g, h}

이렇게 생각해 보았을 때, 각각 d와 h의 값이 정해질 때까지 재귀 호출을 해서 이때까지 구한 숫자들의 합이 Target Number와 동일한지 구해야 한다.

위에서 든 예를 그래프로 나타내보면

(이 그림은 {1, a, b, c, d})인 경우만 나타낸다.

여기서 count 변수를 두어 재귀 호출이 될 때마다 count+1을 해준다.
그래서 count!=numbers.size() 일 때까지 반복하고, 같은 경우에 더해진 합 (그림에서 파란색 숫자)이 Target Number과 같으면 answer+1을 해준다.

#include <string>
#include <vector>

using namespace std;
int answer=0;

void dfs (vector<int> numbers, int target, int sum, int count) {
    if (count==numbers.size()) {
        if (sum==target) answer++;
        return ;
    }

    dfs(numbers, target, sum+numbers[count], count+1);
    dfs(numbers, target, sum-numbers[count], count+1);
}

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

처음에 dfs(numbers, target, 0, 0) 이 호출되면
그래프에서 루트가 1인 경우, -1인 경우로 나누어 진다.
여기서 각각 자식 노드가 +1, -1인 경우의 합으로 나누어 진다.

**코드를 보면 이해하기 쉽지만 처음부터 이렇게 직관적으로 코드 짜는 일은 너무 힘들다..