SWEA3234 준환이의 양팔저울

순열을 이용해 하나씩 저울에 추를 올리며, 우측이 더 무거워지는 경우에는 중단한다.
이런 방식으로 주어진 모든 추를 다 올릴 수 있으면 조건에 맞는 경우를 찾아낼 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
    static int count;

    public static void permutation(int cnt,int left, int right, int[] input, boolean[] isSelected, int N) { // 현재 자리에 수 뽑기.
        if(left < right){
            return;
        }
		if(cnt == N) {
            count++;
			return;
		}	
		// 입력받은 모든 수를 현재 자리에 넣어보기(유도파트)
		for(int i = 0; i < N; i++) {
			// 기존자리의 수들과 중복되는 지 체크.
			if(!isSelected[i]) {
			isSelected[i] = true;
			permutation(cnt + 1, left + input[i], right, input, isSelected, N);
            permutation(cnt + 1, left, right + input[i], input, isSelected, N);
			isSelected[i] = false;
			}
		}
		
	}
    public static void main(String[] args) throws IOException{
        int T = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= T; tc++){
            int N = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine(), " ");
            int[] input = new int[N];
            boolean[] isSelected = new boolean[N];
            for(int i = 0; i < N; i++){
                input[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(input);
            count = 0;
            permutation(0, 0, 0, input, isSelected, N);
            System.out.println("#" + tc + " " + count);
        }
    }
}