[Algorithm] 타겟 넘버

코딩테스트 연습 - 타겟 넘버

 

풀이

주어진 정수형 배열을 더하거나 빼면서 index가 numbers의 길이에 도달했을 때, 연산 결과와 타겟을 비교한다.

DFS로 풀었다. 

 

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