SWEA - 4012 : 요리사 [자바]

조합을 이용해서 풀었는데 A, B 요리 구분을 안 하니까
경우의 수를 반으로 줄일 수 있을 거 같은데..
다시 생각해보기!!

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

public class Solution {
	// 두 명의 손님, 최대한 비슷한 맛의 음식
	// N개의 식재료
	// N/2, N/2개씩 나누어 두 개의 요리(N은 짝수)
	// A음식, B음식의 맛의 차이가 최소가 되도록 재료 배분
	// 식재료 i는 식재료 j와 같이 요리하게 시너지 S_ij 발생
	// 각 음식의 맛은 음식을 구성하는 시너지들의 합

	static int[] A, B;
	static int[][] synergy;
	static int N, diff;

	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 test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine()); // 재료 개수

			diff = Integer.MAX_VALUE;

			synergy = new int[N][N];
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					synergy[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			A = new int[N / 2];
			B = new int[N / 2];
			comb(0, 0);
			sb.append("#").append(test_case).append(" ").append(diff).append("\n");
		}

		System.out.println(sb);
		br.close();

	}

	static void comb(int cnt, int start) {
		if (cnt == N / 2) {

			boolean isSelected[] = new boolean[N];

			for (int i = 0; i < A.length; i++) {
				isSelected[A[i]] =true;
			}
			int count = 0;
			for (int i = 0; i < N; i++) {
				if(!isSelected[i]) B[count++] = i;
			}

			int ABdiff = Math.abs(cal(A) - cal(B));
			diff = Math.min(diff, ABdiff);
			return;
		}

		for (int i = start; i < N; i++) {
			A[cnt] = i;
			comb(cnt + 1, i + 1);
		}
	}

	static int cal(int[] arr) {
		int sum = 0;
		for (int i : arr) {
			for (int j : arr) {
				sum += synergy[i][j];
			}
		}
		return sum;
	}
}