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

입출력 예시
numbers      target     return
[4, 1, 2, 1]       4            2

 

 

 

class Solution {
    
    static int answer = 0; // dfs에서 사용할 수 있도록 전역 변수 선언
    
    public int solution(int[] numbers, int target) {
    
        dfs(numbers, target, 0, 0); // 초깃값으로 depth, sum 모두 0으로 세팅
        return answer;
        
    }
    
    // dfs(Depth-First Search: 깊이 우선 탐색)
    public void dfs(int[] numbers, int target, int depth, int sum) {
        // 마지막 노드까지 탐색을 완료했을 때(= numbers 끝까지 순회 완료)
        if(depth == numbers.length) { 
            if(target == sum) { // target이 sum과 같으면
                answer++; // answer 체크
            }
            return; // 아니라면 필요없기 때문에 null
        }
        // 이전 계층에서 다음 계층으로 내려올 때
        // 양수, 음수 2개가 파생되기 때문에 sum +, sum - 두 번 사용
        dfs(numbers, target, depth+1, sum + numbers[depth]);
        dfs(numbers, target, depth+1, sum - numbers[depth]); 
    }
    
}