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

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

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

풀이

 

재귀함수를 쓰는 DFS로 구현

 

using namespace std;

int dfs(vector<int> numbers, int target, int index, int num);

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


int dfs(vector<int> numbers, int target, int index, int num) {
	int size = numbers.size();
	if (index==size) {
		return num == target ? 1 : 0;
	}
	else {
		return dfs(numbers, target, index+1, num+numbers[index]) + dfs(numbers, target, index+1, num-numbers[index]);
	}
}