[Programmers] 타겟 넘버

난이도 : Level 2

문제링크

• n개의 음이 아닌 정수형 배열이 주어진다
• 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만드는 방법의 수를 리턴하라

 

해설

• 깊이 탐색으로 모든 경우를 조사한다.
• numbers의 길이만큼의 뎁스로 탐색했을 때의 합이 target과 같은지 확인한다.
• 현재 뎁스에서 탐색하려는 숫자의 인덱스는 numbers의 인덱스와 같다.
• 첫번째 수부터 부호를 바꿀 수 있으므로 호출시의 뎁스를 -1로 전달한다

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