타겟 넘버 / 브루트 포스(완탐 DFS)

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

타겟 넘버를 만드는 경우의 수를 구하는 문제였고, n값이 20개 이하로 적은 편이어서 DFS로 완전 탐색으로 문제를 해결하려고 했다.

#include <string>
#include <vector>

using namespace std;

int DFS(vector<int>& numbers, int& target, int idx, int sum)
{
    if (idx == numbers.size())
    {
        return (target == sum) ? 1 : 0;
    }
    
	// 현재 인덱스의 numbers 요소를 더한 경우와 뺀 경우 두 가지 탐색
    return DFS(numbers, target, idx + 1, sum + numbers[idx]) +
        DFS(numbers, target, idx + 1, sum - numbers[idx]);
}

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