[swexpert] 3234. 준환이의 양팔 저울 (java, 완전탐색)

nPr을 먼저해서 n개의 무게추를 순서를 모두 다르게 정렬한 다음

 

subset으로 왼쪽 혹은 오른쪽(왼쪽의 무게가 더 높도록 제한)으로 넘겨주면서 무게를 계산한다.

 

가능한 경우의 수를 리턴한다.

import java.util.ArrayList;
import java.util.Scanner;

public class Solution {
	static int n,t;
	static int weight[];
	static int sum;
	static int answer;
	static  ArrayList<Integer> arr=new ArrayList<>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 1; tc <=t; tc++) {
			n=sc.nextInt();
			answer=0;
			weight=new int[n];
			for (int i = 0; i < n; i++) {
				weight[i]=sc.nextInt();
			}

			nPr(0,0);
				
			System.out.printf("#%d %d\n",tc,answer);
			
		}
		
	}
	private static void subset(int cnt,int left,int right) {
		if(cnt==n) {
			answer+=1;
			return;
		}
		int temp=weight[arr.get(cnt)];
		subset(cnt+1,left+temp,right);
		if(right+temp<=left) {
			subset(cnt+1,left,right+temp);
		}
		
	}
	
	private static void nPr(int cnt,int flag) {
		if(cnt==n) {	
			subset(0,0,0);
			return;
		}
		for (int i = 0; i < n; i++) {
			if((flag&1<<i)!=0)continue;
			arr.add(i);
			nPr(cnt+1,flag|1<<i);
			arr.remove(arr.size()-1);
		}
	}
}
9