[C++] 프로그래머스 타겟 넘버 풀이

주어지는 배열의 원소들을 합하거나 더해서 타겟 넘버로 만들 수 있는 모든 경우의 수를 찾는 문제

 

---

문제의 조건

 

1. 정수가 담긴 배열 numbers, 타겟 넘버 target이 주어짐

 

2. 배열의 모든 숫자를 이용해서 더하고 빼서 target과 같아지는 경우가 몇 개인지 구해서 리턴 

 

---

#include <string>
#include <vector>

using namespace std;

int answer = 0;
void dfs(vector<int>& numbers, int target, int index = 0, int sum = 0)
{
    //마지막 인덱스라면 
    if (index == numbers.size()-1)
    {
        //마지막 바로 앞 원소까지 더한 값에 마지막 원소를 더했을 때 target과 같아진다면 경우의 수 증가
        if (sum + numbers[index] == target) answer++;
        //뺐을 때 target과 같아진다면 경우의 수 증가 
        if (sum - numbers[index] == target) answer++;
        return;
    }

    //배열의 한 원소씩 더하고 인덱스를 증가시켜가며 마지막 원소까지 찾아간다. 
    dfs(numbers, target, index+1, sum + numbers[index]);
    dfs(numbers, target, index+1, sum - numbers[index]);
}

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