깊이 넓이 우선 탐색

class Solution {
    //계산한 값이 target이랑 같아지는 순간까지 재귀함수로 돌린다
    public int dfs(int prev, int idx, int[] numbers, int target) {
        if(idx >= numbers.length){
            if(prev == target){
                //첫번째 숫자부터 같아져 버릴때
                return 1;
            }
            
            //그 어떤 수도 같은게 없을 때
            return 0;
        }
        
        int cur1 = prev + numbers[idx]; //더할 때
        int cur2 = prev - numbers[idx]; //뺄 때
        
        int ans = 0;
        
        ans += dfs(cur1, idx+1, numbers, target);
        ans += dfs(cur2, idx+1, numbers, target);
        
        return ans;
    }
    
    public int solution(int[] numbers, int target) {
        int answer = 0;
        
        int current = numbers[0];
        
        answer += dfs(current, 1, numbers, target);
        answer += dfs(-current, 1, numbers, target);
        
        return answer;
    }
}