[프로그래머스, 43165] 타겟 넘버 (java)

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

728x90

---

메모리: 74.3 MB, 시간: 6.12 ms

사용 알고리즘: DFS

 

class Solution {
    
    static int[] numbers;
    static int target;
    static int answer;
    
    public int solution(int[] numbers, int target) {
        
        this.numbers = numbers;
        this.target = target;
        answer = 0;
        
        dfs(0, 0);
        
        return answer;
    }
    
    private static void dfs(int idx, int num) {
        
        // 마지막 숫자까지 연산 완료
        if(idx == numbers.length) {
            if(num == target) answer++;
            return;
        }
        
        // 더하기
        dfs(idx + 1, num + numbers[idx]);
        // 빼기
        dfs(idx + 1, num - numbers[idx]);
    }
}