[코딩테스트] [프로그래머스] 타겟 넘버

문제

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

---

풀이

1. 깊이 우선 탐색을 통해 각 원소에 + 또는 -를 붙였을 때의 합을 구한다. => 합이 target과 같다면, 1을 반환한다.

2. 재귀함수를 사용해서 현재 index, 현재까지의 합 sum을 인자로 전달해준다.
   2-1. 종료 조건 : 만약 index가 numbers의 크기와 같다면 dfs로 하나의 경우를 모두 탐색했다는 뜻이기에 sum과 target을 비교한다.
   2-2. 다음 단계 : sum에서 numbers[index] 값을 더하거나 빼는 dfs를 각각 수행해 반환 값을 더해준다.

---

코드

#include <iostream>
#include <vector>
using namespace std;

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

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