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

# 문제 내용

프로그래머스: 타겟 넘버

 

# 알고리즘 분류

• DFS/BFS

 

# 풀이

class Solution {
    public int dfs(int prev, int index, int[] numbers, int target) {
        if (index >= numbers.length) {
            if (target == prev) {
                return 1;
            }
            return 0;
        }
        
        // 사칙 연산은 +, - 뿐
        int current_plus = prev + numbers[index];
        int current_minus = prev - numbers[index];
        
        int count = 0;
        count += dfs(current_plus, index+1, numbers, target);
        count += dfs(current_minus, index+1, numbers, target);
        
        return count;
    }
    
    public int solution(int[] numbers, int target) {
        int current = numbers[0];
        int result = 0;
        
        result += dfs(current, 1, numbers, target);
        result += dfs(-current, 1, numbers, target);
        return result;
    }
}