프로그래머스[Java] - (Level2)타겟넘버(dfs)

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

프로그래머스

코드

class Solution {
    
    public static int answer = 0;
    
	public void dfs(int[] numbers, int target, int index){
		// base case:
		if(index == numbers.length){
			int sum = 0;
			for(int i=0; i<numbers.length; i++) 
				sum += numbers[i];

			answer += (sum == target) ? 1 : 0;  /* 합과 target이 같으면 +1 다르면 +0 */
			return;
		}

		dfs(numbers, target, index+1);	/* numbers배열 모두 사용할 때 까지 dfs 탐색 */
		numbers[index] *= -1;		/* 모두 사용 후 base case를 통해 함수 종료하고 전단계로 돌아가서 양수->음수, 음수->양수 */
		dfs(numbers, target, index+1);	/* 위에서 만든 음수로 다시 끝까지 dfs 탐색 */

	}
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0);
        return answer;
    }
}

풀이

배열의 모든 요소를 더하거나 빼서 target 넘버를 만드는 방법의 수를 return,

더하거나 빼는 연산과정을 Tree로 볼때, '+'연산은 왼쪽 자식노드, '-'연산은 오른쪽 자식 노드로 내려가는 과정으로 재귀호출을 통해 해결한다.(깊이우선탐색, dfs)

기저 사례는 배열의 모든 요소를 사용할 때(index == numbers.length) 이다.

https://lkhlkh23.tistory.com/74

위 과정을 잘나타낸 이미지가 있어서 참고했다.