programmers 타겟 넘버

programmers : https://programmers.co.kr/learn/courses/30/parts/12421

 

깊이/너비우선탐색 분류 level2 타겟넘버 입니다.

 

고려해야할 사항은 숫자가 최대 20가지이기 때문에, 무난히 dfs로 재귀만 돌려주셔도 해결할 수 있습니다.

 

#include <string>
#include <vector>
using namespace std;
 
int answer, len, want;
vector<int> v;
 
void solve(int sum, int idx){
    if(idx == len){
        if(sum == want)
            answer++;
        return;
    }
    
    solve(sum + v[idx], idx+1);
    solve(sum - v[idx], idx+1);
}
 
int solution(vector<int> numbers, int target) {
    len = numbers.size();
    want = target;
    for(int i = 0; i<len; i++) v.push_back(numbers[i]);
    solve(0, 0);
    return answer;
}