자바 | 프로그래머스 | 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 

class Solution {
    static int answer;
    public int solution(int[] numbers, int target) {
        answer = 0;
        dfs(0, 0, 0, numbers.length, numbers, target);
        return answer;
    }
  
    void dfs(int cnt, int start, int res, int N, int[] numbers, int target){
        if (cnt==N){
            if (res==target){
                answer++;
            }
            return;
        }
        
        for (int i=start; i<N;i++){
            dfs(cnt+1, i+1, res+numbers[i], N, numbers, target);
            dfs(cnt+1, i+1, res-numbers[i], N, numbers, target);
        }
    }
    
}

완탐 문제
경우의 수는 더하거나 빼거나 두 가지로 각각의 경우를 dfs를 돌려 모두 탐색한다.