[Programmers] Level2 : 타겟 넘버

Question

---

Solution

• 조건을 만족하는 경우의 수를 찾아야 하기 때문에 완전탐색을 한다.
• 재귀를 통하여 +- 부호 각각 연산을 하여 마지막 노드에 도달하였을때 target과 일치하면 카운팅 하면 된다.

---

Cord

#include <string>
#include <vector>

using namespace std;

vector<int> copyNums;
int cnt = 0;

void dfs(int node, int sum, int target)
{
    // 마지막 도달 시 총합 확인
    if (node == copyNums.size()-1)
    {
        if (sum == target) { ++cnt; }
        return;
    }
    
    // +- 부호에 대한 각각 탐색
    for (int i = 0; i < 2; ++i)
    {
        if (i == 0) { dfs(node+1, sum+copyNums[node+1], target); }
        else { dfs(node+1, sum-copyNums[node+1], target); }
    }
}

// 완전탐색 + dfs
int solution(vector<int> numbers, int target) 
{
    int answer = 0;
    copyNums = numbers;  
    dfs(-1, 0, target);
    
    return answer = cnt;
}

---

Result