프로그래머스 자바 :: 타겟넘버 (DFS)

재귀함수~~

 

 

 

 

 

class Solution {
    
    int count = 0;
    
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        dfs(numbers, target, 0, 0);
        answer = count;
        
        return answer;
    }
    
    public void dfs(int[] numbers, int target, int depth, int result){
        
        if(depth == numbers.length){
            if (result == target){
                count++;
            }
            return; // 이거 잊지말자!! result랑 target 같지 않아도 리턴되게!!
        }
        
        int plus = result + numbers[depth];
        int minus = result - numbers[depth];
        
        dfs(numbers, target, depth+1, plus);
        dfs(numbers, target, depth+1, minus);
    }
}

 

 

 

---

간단한 다른사람 풀이

 

 

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