[프로그래머스/Level 2] 타겟 넘버 (C++)

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

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

전형적인 DFS 문제였습니다.

 

#include <string>
#include <vector>
using namespace std;

int answer;

void DFS(int L, int sum, vector<int> numbers, int target) {
    if(L == numbers.size()) {
        if(sum == target) answer++;
        return;
    } else {
        DFS(L + 1, sum - numbers[L], numbers, target);
        DFS(L + 1, sum + numbers[L], numbers, target);
    }
}

int solution(vector<int> numbers, int target) {
    DFS(0, 0, numbers, target); // DFS Level(인덱스), 합, 벡터, 타겟넘버
    return answer;
}