27. LEVEL 2 - 타겟 넘버 - DFS/재귀

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

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

class Solution {
    public int solution(int[] numbers, int target) {        
        int answer = 0;
        
        int result1 = dfs(numbers, numbers[0], target, 1);
        int result2 = dfs(numbers, -numbers[0], target, 1);
        answer = result1 + result2;        
        return answer;
    }
	
	public int dfs(int[] numbers, int sum, int target, int i) {
		
		int result = 0; 
		
		if(i == numbers.length) {	// 배열 마지막 인덱스 까지 같을때
			if(sum == target)	// 합계가 target과 같으면 +1
				return 1;
			else
				return 0;
		}
		
		result += dfs(numbers, sum + numbers[i], target, i+1);	// 양수
		result += dfs(numbers, sum - numbers[i], target, i+1);	// 음수
		return result;
	}	
}

- dfs는 재귀로도 구현이 가능하고, 스택을 사용해서도 구현이 가능함

- 재귀 함수는 항상 재귀를 끝내는 부분과 재귀 호출을 하는 부분으로 나뉜다.

- 재귀 함수안에서는 반복문은 X

- 아래와 같이 재귀적으로 반복된다고 생각하면 됨 : 재귀 호출하면서 마지막 노드(i == numbers.length)까지 갔을때 합계(sum)가 target과 같으면 +1 카운팅