프로그래머스 | LV.2 타겟 넘버 문제 - DFS 문풀 (Java)

⬛ 프로그래머스 | LV.2  타겟 넘버 문제  - DFS 문풀

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

프로그래머스

 

---

💚나의 풀이 

• 일단 각 배열의 값의 순서는 조절 X
• 배열의 각 idx별 값은 1) 더하거나 2) 빼는 경우만 있다.
• dfs로 해당의 경우를 깊이 탐색하며 끝에 다다랐을 때의 sum 값이 target과 일치할 때만 answer++;처리

class Solution {
    static int answer =0;
    //dfs
    static void dfs(int idx, int sum , int[] numbers, int target){
        if(idx == numbers.length){
            if(sum == target){
                answer++;
            }
        }
        else{
            dfs(idx+1, sum+numbers[idx], numbers, target);
            dfs(idx+1, sum-numbers[idx], numbers, target);
        }
    }
    
    //솔루션 함수 
    public int solution(int[] numbers, int target) {
            
        dfs(0, 0, numbers, target);
        
        return answer;
    }
}