타겟 넘버

문제풀이 흐름

선택의 기로에 놓여있다...
더해주는가, 빼주는가

깊이우선 탐색으로 하나를 기준으로 더하기,빼기를 골고루 쭉 계산해본다.
idx가 배열의 길이이면 이미 다 돌았다는 이야기 이므로, sum == target의 값이 일치하면 answer++을 해주고 최종적으로 return 해준다.

크게 2가지 경우를 계속 탐색해준다.
(1) dfs 다음 숫자를 더해준 경우
(2) dfs 다음 숫자를 빼준 경우

그리기 복잡해서 다 그리지는 못했지만, 이런 트리구조를 가진다.

class Solution {
    
    static int answer;
    
    public int solution(int[] numbers, int target) {
        dfs(0,0,numbers,target);

        return answer;
    }

    public static void dfs(int sum, int idx, int[] numbers, int target){ // 변수값 저장하기

        if(idx == numbers.length){
            if(sum == target){
                answer++;
            }

            return;
        }

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