문제 바로가기

접근방식

-,+ 을 적절하게 섞어서 target숫자 만들기
처음엔 그냥 다 더해서 완전탐색으로 -가 들어갈 자리를 찾으면 안되나 생각했다. 그러나 이렇게 푸는 것보다 그때그때 -,+ 자리를 지정해주는 방법을 선택했다.

정답코드

import java.io.*;
import java.util.*;

class Solution {
    static int answer;
    static int[] n;
    static int t;
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        n=numbers;
        t=target;
        
        perm(0,0);
        
        return answer;
    }
    
    static void perm(int idx, int sum){
        if(idx==n.length){
            if(sum==t){
                answer++;
            }
            return;
        }
        
        perm(idx+1,sum+n[idx]);
        perm(idx+1,sum-n[idx]);
    }
}