프로그래머스 타겟넘버 c++ // dfs

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=cpp 

프로그래머스

1. 의사코드

최악 : 2^20 == 1048576  < 1억 이므로

완탐가능하다.

모든넘버에대해 -, + 경우를 가정하고

dfs로 완탐한다.

 

 

2. 전체코드

#include <string>
#include <vector>

using namespace std;

int answer;

void dfs(vector<int>& numbers, int& target, int idx, int result){
    
    if(idx==numbers.size()){
        if(result==target){
            answer++;
        }
        return;
    }
    
    dfs(numbers,target,idx+1,result-numbers[idx]);
    dfs(numbers,target,idx+1,result+numbers[idx]);
}

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