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

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

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

 

#include <string>
#include <vector>

using namespace std;

int cnt=0;

void dfs(vector<int>& numbers, int target, int depth, int limit, int result){
    if (depth==limit){
        if (result==target){
            cnt++;
        }
        return;
    }
    dfs(numbers, target, depth+1, limit, result+numbers[depth]);
    dfs(numbers, target, depth+1, limit, result-numbers[depth]);
}

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

DFS 를 이용하여 탐색하는 문제.

 

1 depth마다 2가지 경우의 수가 존재한다.(더하느냐, 빼느냐).

DFS 방식으로 탐색한다. 이때 depth가 limit이면(즉 numbers의 크기이면), 그간의 결과값이 target 과 일치하는지 체크한다.