[알고리즘/SWEA] #3234 준환이의 양팔저울

package algorithm_lab.day12.q2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SWEA_3234 {
	
	static int N,ans;
	static int[] input,res;
	static boolean[] chk;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1;t<=T;t++) {
			N=Integer.parseInt(br.readLine());
			
			input= new int[N];
			chk= new boolean[N+1];
			res=new int[N];
			ans=0;
			
			String[] s =br.readLine().split(" ");
			for(int i=0;i<N;i++) {
				input[i]=Integer.parseInt(s[i]);
			}
			perm(0);
			sb.append("#").append(t).append(" ").append(ans).append("\n");
			
		}
		System.out.print(sb.toString());
	}
	
	public static void perm(int cnt) {
		if(cnt==N) {
			ch(0,0,0);
			return;
		}
		for (int i=0;i<N;i++) {
			if(chk[i]) continue;
			chk[i] = true;
			res[cnt]=input[i];
			perm(cnt+1);
			chk[i]=false;
		}
	}
	public static void ch(int idx, int sl, int sr) {
		if(idx==N) {
			ans++;
			return;
		}
		ch(idx+1,sl+res[idx],sr);
		if(sr+res[idx]<=sl) ch(idx+1,sl,sr+res[idx]);
	}
}