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

문제

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

프로그래머스

 

풀이

사실 dfs/bfs 유형이라고 적혀 있는데, 어떻게 풀어야 할지 감이 오지 않았다.

질문하기의 위 글을 보고 코드를 짤 수 있었다.

 

코드

#include <string>
#include <vector>

using namespace std;

void dfs(int idx, const vector<int> &numbers, int sum, int target, int& answer){
    // 종료 조건
    if(idx==numbers.size()){
        if(sum==target){
            answer++;
        }
        return;
    }
    
    // 재귀 호출
    dfs(idx+1, numbers, sum+numbers[idx], target, answer);
    dfs(idx+1, numbers, sum-numbers[idx], target, answer);
}

int solution(vector<int> numbers, int target) {
    int answer = 0;
    dfs(0, numbers, 0, target, answer);
    
    return answer;
}