[Divide and Conquer 예제] 프로그래머스 Level2 타겟넘버

문제

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

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

 

---

문제 풀이

#include <string>
#include <vector>

using namespace std;
int answer = 0;
void dfs(vector<int> numbers, int target,int sum, int count){
    if(count == numbers.size()){
        if(sum == target) answer++;
        return;
    }
    //dfs : -1의 부호, count --
    dfs(numbers, target, sum + numbers[count],count+1);
    //dfs : 1의 부호, count --
    dfs(numbers, target, sum - numbers[count],count+1);
}

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

간단한 분할정복 dfs 문제이다.

근데 여기서 주의해야할 점은,

(1) void dfs는 되는데 int dfs()는 오류가 난다. return 0으로 처리를 해도 오류가 나는데, 이유를 모르겠다.

(2) recursion 함수 매개변수에 count ++ 가 아닌 count+1으로 작성