[프로그래머스] (깊이/너비 우선 탐색) 타겟 넘버

입력 배열 노드를 순차로 탐색 하면서 매 탐색시 양갈래(지나온 노드들의 sum에서 현재노드를 +하는 경우, -하는경우) 로 탐색하며 재귀호출 하여 마지막 노드에 도달했을때 노드들의 sum이 타겟 넘버와 같으면 타겟 적중을 +1 한다.

 

index로 양쪽(+-) 탐색을 하는 재귀함수를 만들면 된다.

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        answer = calcNum(numbers, 0, target, 0);
        return answer;
    }
    
    public static int calcNum(int[] source, int index, int target, int sum) {
        // 마지막 노드에 도달했을 때
        if(index == source.length) {
            // 타겟 넘버와 누적 sum이 같으면 + 1
            if(target == sum) {
                return 1;
            } else {
                return 0;
            }
        }

        return calcNum(source, index+1, target, sum + source[index])
                + calcNum(source, index+1, target, sum - source[index]);

    }
}

 

출처: 프로그래머스 코딩 테스트 연습, 
https://programmers.co.kr/learn/challenges