[프로그래머스 C++] 43165. 타겟 넘버

문제 링크

---

프로그래머스

 

접근 방법

---

더하는 경우와 빼는 경우 2가지로 깊이 우선 탐색을 하였습니다.

소스 코드

---

#include <string>
#include <vector>

using namespace std;

int cnt = 0;

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

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

    return cnt;
}