[JAVA] 타겟 넘버

'+' 와 '-' 를 모든 경우에 대입하여 알아보는 문제이므로, 부분집합을 이용해서 선택되면 +를 안되면 -를 연산하도록 했다.

 

class Solution {
    
    static int count;
    
    public int solution(int[] numbers, int target) {
        int answer = 0;
        boolean[] add = new boolean[numbers.length];
        subset(0,add,numbers,target);
        answer = count;
        return answer;
    }
    
    private static void subset(int cnt, boolean[] add, int[] numbers, int target){
        if(cnt == numbers.length){
            int sum = 0;
            for(int i=0;i<add.length;i++){
                if(add[i]) sum += numbers[i];
                else sum -= numbers[i];
            }
            if(sum == target) count++;
            return;
        }
        add[cnt] = true;
        subset(cnt+1, add, numbers, target);
        add[cnt] = false;
        subset(cnt+1, add, numbers, target);
    }
}

 

다른 분의 우수한 dfs코드이다!! 원래 이 문제는 dfs/bfs로 분류되어 있던 문제이다.

 

우수 풀이