[프로그래머스] 레벨 2 - 타겟 넘버

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

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

전형적인 DFS 문제다. 

현재 인덱스의 숫자를 더한 것의 재귀와

현재 인덱스의 숫자를 뺀 것의 재귀를 이어나가 최종 길이만큼 연산을 수행한 뒤, 결과를 tg_num과 비교해 답을 추가한다.

 

100번째 포스팅!

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