타겟 넘버

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

프로그래머스

 

역시나 전형적인 DFS 문제.

 

numbers에 있는 값을 더하는 로직 1개와 빼주는 로직 1개를 같이 호출해주고,

 

모든 숫자에 대한 처리가 끝났을 때 target 넘버와 비교하면 끝.

 

class Solution {
    
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        
        calc(numbers, target, 0, 0);
        return answer;
    }
    
    void calc(int[] numbers, int target, int idx, int sum) {
        
        if (idx == numbers.length) {
            if (target == sum) answer++;
            return;
        }
        
        calc(numbers, target, idx + 1, sum + numbers[idx]);
        calc(numbers, target, idx + 1, sum - numbers[idx]);
        
    }
    
}