[level2] 프로그래머스 - 타겟 넘버(JAVA)

 

 

- dfs를 응용하여 각 숫자를 더했다가 빼보면 된다.
   그러면 numbers의 숫자를 빼고 더하는 모든 경우의 수에 대해 탐색 가능!

 

 

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

        makeTargetNum(numbers, target, 0, 0);

        return answer;
    }

    static void makeTargetNum(int[] numbers, int target, int cnt, int sum) {
        if(cnt == numbers.length) {
            if(sum == target)
                answer++;
            return;
        }

        makeTargetNum(numbers, target, cnt + 1, sum - numbers[cnt]);
        makeTargetNum(numbers, target, cnt + 1, sum + numbers[cnt]);
    }
}