[프로그래머스] #lv.3 - 타겟 넘버 (Java)

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

프로그래머스

 

# 힌트

DFS를 상태 공간 트리를 탐색하는 용도로 사용하는 문제이다.

해당 숫자를 더하는 경우와 빼는 경우 둘 다 DFS를 진행한다.

이런 식으로 상태 공간 트리를 그려보면 이해하기 쉬울 것이다.

 

해답 보기

# 해답

layer : 현재 상태 공간 트리의 계층 (이 값은 numbers의 값 + 1과 동일하다. 1은 첫 번째 시작 노드)

sum : 현재까지의 숫자를 더한 값

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

    static int count = 0;

    static void dfs(int target, int sum, int layer, int[] numbers) {
        if (layer >= numbers.length && sum == target) count++;
        else if (layer >= numbers.length) return;
        else {
            dfs(target, sum + numbers[layer], layer + 1, numbers);
            dfs(target, sum - numbers[layer], layer + 1, numbers);
        }
    }
}