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

 

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

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

 

재귀함수를 이용한 dfs를 사용해 되는 문제

 

재귀함수에 sum과 idx와 방문하는 숫자(x)를 넘긴다.

 

재귀함수는 방문하는 숫자(x)를 sum에 더하면서 시작한다.

 

이후에

1. numbers[idx]에 -1을 곱한 걸로 dfs 재귀함수에 넘기고

2. 그냥 numbers[idx]를 dfs 재귀함수에 넘긴다.

 

그러면 모든 경우의 수가 재귀함수로 돌면서 생길꺼고

 

재귀중단 조건문은 idx가 numbers.size()-1일때 멈추고

 

그때의 sum값이 target과 같다면 answer를 +1 한다.

 

 

 

 

Code

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int answer;

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

int solution(vector<int> numbers, int target) {
    int start = numbers[0];
    dfs(start, 0, target, 0, numbers);
    dfs(-1*start, 0, target, 0, numbers);
    
    return answer;
}