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

문제

---

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

풀이

---

원하는 숫자를 만들 수 있는 경우의 수를 구하는 문제로, DFS를 통해 조건을 충족하는 경우의 수를 모두 더해 return한다.

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void DFS(vector<int> numbers, int target, int sum, int idx)
{

    if (idx == numbers.size())
    {
        if (sum == target)
        {
            answer++;
        }
        return;
    }

    DFS(numbers, target, sum + numbers[idx] ,idx + 1);
    DFS(numbers, target, sum - numbers[idx], idx + 1);
}

int solution(vector<int> numbers, int target)
{
    int sum = 0;
    int idx = 0;

    DFS(numbers, target, sum, idx);


    return answer;
}