프로그래머스 - 타겟 넘버(c++)

이 문제는 처음에 브루트 포스로 접근하였는데, 시간 초과가 나서 dfs를 이용하여 해결하였다.

아직도 재귀 로직이 헷갈려서 고생했다. 관련 유형을 더 풀어볼 예정이다. 

void dfs(vector<int> numbers, int sum, int target, int index) {


	if (index == numbers.size() -1) {
		if (sum+numbers[index] == target) {
			
			cnt++;

		}
		if (sum - numbers[index] == target) {
			
			cnt++;
		}
		return;
	}

	

	

	dfs(numbers, sum+numbers[index], target, index+1);
	
	dfs(numbers, sum - numbers[index], target, index+1);



}

만약 1,2,3,4인 배열을 넣으면

1 2 3 4 /1 2 3 -4

1 2 -3 4/ 1 2 -3 -4

... 

이런 식으로 들어감을 유의하자