타켓 넘버

문제 링크

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

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

 

문제 풀이 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int N=0;
int T=0;
int A=0;

void dfs(vector<int> numbers, int cnt, int sum){//N=5, T=3
    
    if(cnt==N){
        if(sum==T) A++;
        return;
    }
    else{
        dfs(numbers, cnt+1, sum+numbers[cnt]);
        dfs(numbers, cnt+1, sum-numbers[cnt]);
    }
    
}
int solution(vector<int> numbers, int target) {
    
    int answer = 0;
    
    N=numbers.size(); T=target;
    
    dfs(numbers, 0, 0);
    
    answer=A;
    
    return answer;

}

항상 느끼는 거지만 재귀 문제는 탈출 조건을 고려하는 것이 가장 중요한 것 같다.