(C++) - 프로그래머스(고득점 kit - (DFS/BFS)) : 타겟 넘버(DFS) 답

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

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

dfs로 푼 문제였습니다.

풀이방법

 1. 빼거나 더해서 depth == size까지  target과 같다면 1을 반환, 아니라면 0을 반환

 2. dfs함수 호출 후 cnt를 반환

 

 

Code

#include <bits/stdc++.h>

using namespace std;
int dfs(int depth, int num, vector <int> &numbers, int target){
    if(depth == numbers.size()){
        return num == target;
    }
    int cnt = 0;
    cnt += dfs(depth+1, num + numbers[depth], numbers, target);
    cnt += dfs(depth+1, num - numbers[depth], numbers, target);
    return cnt;
}

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