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

DFS/BFS 감을 되찾고자 레벨 2의 타겟 넘버 문제를 풀었다.

 

나는 DFS를 선택해 문제를 풀었다. 

 

// numbers 배열에 숫자들의 목록이 들어있음
// 배열의 숫자들을 각 단계에서 더하거나 빼서
// target이 나올 수 있는 경우를 카운트해서 반환.
// DFS/BFS 사용하는 것이 좋아보임
class Solution {
    static int result = 0;
    
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }
    
    // numbers: 숫자 배열
    // target: 목표값
    // idx: 숫자 배열의 인덱스
    // compute: 계산된 값
    public int dfs(int[] numbers, int target, int idx, int compute){
        if(numbers.length == idx ){
            if(compute == target){
                return 1;
            }
            return 0;
        }
        
        return dfs(numbers, target, idx + 1, compute + numbers[idx]) + dfs(numbers, target, idx + 1, compute - numbers[idx]);
    }
}