프로그래머스. 타겟 넘버(c++) / DFS

기본적인 dfs문제라고 생각된다.

numbers.size()만큼 dfs를 돌면서 계산을 해주고 최종 결과가 target값과 동일하면 answer++해주면 된다.

 

#include <string>
#include <vector>
 
using namespace std;
 
int answer = 0;
 
void dfs(int num, int idx, int target, vector<int> numbers)
{
    if(idx==numbers.size()){
        if(num==target){
            answer++;
        }
        return;
    }
    
    dfs(num+numbers[idx], idx+1, target, numbers);
    dfs(num-numbers[idx], idx+1, target, numbers);
}
 
int solution(vector<int> numbers, int target) {    
    dfs(0, 0, target, numbers);
    
    return answer;
}