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

[문제링크 - 프로그래머스 - 타겟 넘버] https://school.programmers.co.kr/learn/courses/30/lessons/43165

class Solution {
    static int answer = 0;
    public int solution(int[] numbers, int target) {
        dfs(0, 0, target, numbers);
        return answer;
    }

    public void dfs(int i, int sum, int target, int[] numbers){
        if(i == numbers.length){
            if(sum == target){
                answer++;
            }
        }
        else{
            dfs(i+1, sum-numbers[i], target, numbers);
            dfs(i+1, sum+numbers[i], target, numbers);
        }
    }
}

• -하는 경우의 수와 +하는 경우의 수로 나눠지므로 각각에 대해 dfs()를 호출한다.
• 계속 아래로 뻗어나가다가 numbers의 갯수와 같아지면 sum == target 인지 확인한다.