프로그래머스 타겟 넘버

 

2의 19승이니까 1초 안에 통과할 수 있다.

1억 미만이기에!

 

#include <string>
#include <vector>

using namespace std;

int result = 0;

// 2의 19승 = 52만
void dfs(vector<int>& numbers, int target, int start, int value) {
    if(start == numbers.size()) {
        if(value == target)
            result++;
        return;
    }
    
    dfs(numbers, target, start + 1, value + numbers[start] * 1);
    dfs(numbers, target, start + 1, value + numbers[start] * -1);
}

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

추천수가 가장 많은 풀이보다 내 풀이가 더 좋다 ㅎㅎ