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

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

코딩테스트 연습 - 타겟 넘버

dfs를 이용하여 모든 가능한 경우의 수를 구하고, 각 경우의 수가 target 과 일치하는지를 확인해서 값을 반환합니다.

class Solution {
    public int findAnswer(int[] numbers, int target, int idx, int prevNum) {
        if (idx == numbers.length) {
            return prevNum != target ? 0 : 1;
        }
        return findAnswer(numbers, target, idx + 1, prevNum + numbers[idx]) + findAnswer(numbers, target, idx + 1, prevNum - numbers[idx]);
    }

    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer = findAnswer(numbers, target, 0, 0);
        return answer;
    }
}