[JAVA 문제 풀이] 330. 타겟 넘버

내가 작성한 코드

class Solution {
    public int solution(int[] numbers, int target) {
        // DFS 탐색 시작: 인덱스 0부터, 누적합은 0
        return dfs(0, numbers, target, 0);
    }

    // DFS 함수: 현재 인덱스, 숫자 배열, 목표값, 현재까지의 누적합
    public int dfs(int idx, int[] numbers, int target, int sum) {
        // 모든 숫자를 다 사용한 경우 (리프 노드 도달)
        if (idx == numbers.length) {
            // 누적합이 target과 같으면 유효한 경우이므로 1을 반환
            if (sum == target) {
                return 1;
            }
            // 아닌 경우는 유효하지 않으므로 0을 반환
            return 0;
        }

        // 현재 숫자를 더하는 경우와 빼는 경우를 각각 탐색
        // 두 경우의 결과를 합쳐서 리턴 (가능한 조합 수 누적)
        return dfs(idx + 1, numbers, target, sum + numbers[idx]) 
             + dfs(idx + 1, numbers, target, sum - numbers[idx]);
    }
}