[프로그래머스] 타겟 넘버 - 자바

프로그래머스 타겟 넘버 

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

프로그래머스

 

아이디어

• DFS(깊이 우선 탐색) 을 활용해서 모든 경우의 수를 탐색해본다
• 깊이가 배열의 길이보다 커지면 스택오버플로우가 발생하기 때문에 DFS깊이가 배열의 크기와 같을 때 확인한다
• 크기가 같고 우리가 찾는 숫자인 'target' 이라면 count++ 증가 시킨다
• 그렇지 않으면 depth + 1 로 늘려주고, 배열의 다음숫자를 더하고, 뺄셈을 하여 탐색한다

코드

class Solution {
    public static int count;
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0); // 처음은 깊이가 0, 합이 0
        return count;
    }
    
    public static void dfs(int[] numbers, int target, int depth, int result) {
        if (numbers.length == depth) {
            if (result == target) {
                count++;
            }
        }
        else {
            dfs(numbers, target, depth+1, result + numbers[depth]);
            dfs(numbers, target, depth+1, result - numbers[depth]);
        }
    }
}