Programers 타켓넘버

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

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

프로그래머스 타켓넘버 문제입니다.

#include <string>
#include <vector>

using namespace std;
vector<int> num;
int tar;
int sol;
void dfs(int sum, int n){
    if((n-1) == 0){
        if(sum+num[n-1] == tar || sum-num[n-1] == tar)
            sol++;
        return;
    }
    
    dfs(sum + num[n-1],n-1);
    dfs(sum - num[n-1],n-1);
    return; 
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    for(auto iter : numbers)
        num.push_back(iter);
    
    tar = target;
    dfs(0,num.size());
    answer = sol;
    return answer;
}

아이디어

DFS 이용했습니다.