Programmers_타겟 넘버

단순 재귀를 이용해서 풀었습니다. 쉽게 생각하면 쉽고 어렵게 생각하면 어려운 문제인듯 하네요.

• 숫자는 움직이지 않고, 부호만 움직이는 식으로 풀었다.
• 재귀를 이용하여 각각 두 개의 재귀로 +,- 넣어주고, 해당 수만큼 넣어줬을 때, target값과 비교하여 answer를 증가시켜줬다.

💻 전체 코드

#include <string>
#include <vector>

using namespace std;

int answer = 0;

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

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