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

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

 

Idea

BFS/DFS 문제는 최단거리냐 아니냐로 판단하는 편인데, 이 문제는 최단거리는 아니어서 DFS 방식으로 풀었다.

if (index == numbers.length) 여기에서 numbers.length - 1 이 아닌 이유는 마지막 인덱스를 탐색한 후에 더 이상 진행하지 않기 때문이다. index == numbers.length 는 배열의 끝을 넘어선 인덱스라는 의미로, 배열을 다 탐색한 후 종료 조건을 만족하고 재귀를 종료한다.

 

 

Code

class Solution {
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, 0);
        return answer;
    }
    
    private void dfs(int[] numbers, int target, int index, int sum) {
        if (index == numbers.length) {
            if (target == sum) {
                answer++;
            }
        }
        else {
            dfs(numbers, target, index + 1, sum + numbers[index]);
            dfs(numbers, target, index + 1, sum - numbers[index]);
        }
    }
}