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

15 May 2021

Reading time ~1 minute

DFS를 활용한 가장 대표적 문제(다시 풀기)

문제를 보고 바로 dfs임을 알 수 있어아햠!
참조형 변수의 활용에 유의!
재귀호출은 반복문과 같은 효과를 지니기 때문에 재귀에서 반복문은 생각하지 않는다
재귀 종료조건1 : 배열 index가 numbers 벡터 끝
재귀 종료조건2 : target과 sum 비교

#include <string>
#include <vector>

using namespace std;

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

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