프로그래머스 : 타겟넘버(C++, Lv.2, DFS)

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

재귀를 통한 DFS방법으로 문제를 풀어보았다.

 

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(vector<int> numbers, int taget,int sum, int cnt) {
    if(cnt==numbers.size()) {
        if(taget == sum) answer++;
        return;
    }
    
    dfs(numbers, taget, sum+numbers[cnt], cnt+1);
    dfs(numbers, taget, sum-numbers[cnt], cnt+1);
}


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