[알고리즘] Level2 ) 타겟넘버 C++ 구현 ( DFS 이용 )

#include <string>
#include <vector>
#include <iostream>
using namespace std;


int answer = 0;

void dfs(int index, int sum , int target , vector<int> numbers) {
	
	if (index == numbers.size()) { // numbers 의 마지막 원소까지 간 경우
		if (sum == target) { // sum 이 target 과 같으면
			answer++; 
		}
		return;
	}
	dfs(index+1, sum+numbers[index], target, numbers); // 더하는쪽으로
	dfs(index+1, sum-numbers[index], target, numbers); // 빼는쪽으로
}

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

void main() {
	vector<int> numbers = { 1,2,3,4,5 };
	int target = 5;
	cout << solution(numbers, target) << endl;
}