[프로그래머스] 43165 타겟 넘버 - JAVA - Lv.2

[프로그래머스] 43165 타겟 넘버 - JAVA - Lv.2

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

문제 분석

조건

• 자연수 배열이 주어지면 배열의 각 수를 더하거나 빼서 타겟 넘버를 맞추는 문제이다.

풀이방법

• 재귀 함수를 사용하는 DFS를 사용하여 문제를 해결한다.

코드

class Solution {
    public static int TG;
    public static int SIZE;
    public static int answer;
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        TG = target;
        SIZE = numbers.length;
        
        dfs(0,numbers, 0);
        
        return answer;
    }
    
    public void dfs(int depth,int[] numbers,int curr){
        if(depth == SIZE){
            if(curr == TG){
                answer++;
                return ;
            }else{
                return ;
            }
        }
        
        dfs(depth+1, numbers, curr+numbers[depth]);
        dfs(depth+1, numbers, curr-numbers[depth]);
        
    }
}

결과