타겟 넘버

알고리즘 분류는 dfs/bfs 인 문제이다. level2문제로 전형적인 재귀 문제였다...!

바로 코드를 첨부하겠습니당

 

#include <string>
#include <vector>

using namespace std;

void dfs(vector<int> numbers, int target, int i,int& answer, int result){
    
    if(i == numbers.size()){
        if(result == target)answer++;   
        return;
    }
    
    dfs(numbers,target, i+1, answer, result+numbers[i]);
    dfs(numbers,target, i+1, answer, result-numbers[i]);
}
int solution(vector<int> numbers, int target) {
    int answer = 0;
    dfs(numbers, target, 0, answer, 0);
    return answer;
}

재귀 탈출 조건은 i가 최대 인덱스 범위를 넘어갔을 때, 즉 모든 numbers를 돌아봤을 때 결과가 target과 같다면 결과를 더해주고 return 해줍니다.