[프로그래머스/완전탐색] 타겟 넘버

<접근>
numbers의 숫자들을 모두 사용해야함 -> dfs or bfs

재귀를 통해 dfs를 적용하였다

numbers의 숫자를 더하거나 빼거나 경우가 2가지로 나누어 지므로

두가지 경우를 따로 재귀함수 작성

숫자들을 모두 사용해 (+) or (-) 한 결과가 target과 같으면 answer ++

<시간복잡도>

??

#include <string>
#include <vector>

using namespace std;

int answer = 0;

// cur_index : nubers에서 사용할 숫자 index
// cur_num : 현재까지 계산한 결과
void dfs(vector<int> &numbers, int target, int cur_index, int cur_num)
{
    if (cur_index == numbers.size()) // cur_index == numbers.size() -1 이 아닌 이유는, 마지막 숫자도 더하거나 빼줘야 하기 때문
    {
        if (cur_num == target)
        {
            answer++;
            return;
        }
    }
    else
    {
        // cout << cur_index << ' ' << cur_num << '\n';

        int cur_num_plus = cur_num + numbers[cur_index];
        dfs(numbers, target, cur_index + 1, cur_num_plus);

        int cur_num_minus = cur_num - numbers[cur_index];
        dfs(numbers, target, cur_index + 1, cur_num_minus);
    }
}

int solution(vector<int> numbers, int target) {

    dfs(numbers, target, 0, 0);
    
    return answer;
}