Решение для динамического программирования
import java.util.HashMap;
import java.util.Map;
public class Balanced01Matrix {
//Variable to hold all possible row permutation
private int[][] rowPerms;
//Mapping function f((n/2,n/2),(n/2,n/2)......(n/2,n/2))
Map<String, Integer> arrangeFunction;
int rowCounter = 0;
/**
* @param args
*/
public static void main(String[] args) {
Balanced01Matrix bm = new Balanced01Matrix();
int n = 4;
int rows = bm.combination(n, n/2);
bm.rowPerms = new int[rows][n];
//Getting all the row permuation with n/2 '0' and n/2 '1'
bm.getAllCombination(n/2, n/2, n, new int[n]);
//bm.printAllCombination();
bm.arrangeFunction = new HashMap<String, Integer>();
//Variable to hold vector ((n/2,n/2),(n/2,n/2),......(n/2,n/2))
int[][] digitsRemaining = new int[n][2];
for(int i=0;i<n;i++){
digitsRemaining[i][0]=n/2;
digitsRemaining[i][1]=n/2;
}
//Printing total number of combination possible for nxn balanced matrix
System.out.println(bm.possibleCombinations(digitsRemaining, n));
}
/**
* Method to get all permutation of a row with n/2 zero and n/2 one
* @param oneCount
* @param zeroCount
* @param totalCount
* @param tmpArr
*/
private void getAllCombination(int oneCount, int zeroCount, int totalCount, int[] tmpArr){
if(totalCount>0){
if(oneCount > 0){
tmpArr[totalCount-1] = 1;
getAllCombination(oneCount-1, zeroCount, totalCount-1, tmpArr);
}
if(zeroCount > 0){
tmpArr[totalCount-1] = 0;
getAllCombination(oneCount, zeroCount-1, totalCount-1, tmpArr);
}
}else{
rowPerms[rowCounter++] = tmpArr.clone();
}
}
/**
* Recursive function to calculate all combination possible for a given vector and level
* @param digitsRemaining
* @param level
* @return
*/
private int possibleCombinations(int[][] digitsRemaining, int level){
//Using memoization
if(arrangeFunction.containsKey(getStringForDigitsRemaining(digitsRemaining))){
return arrangeFunction.get(getStringForDigitsRemaining(digitsRemaining));
}
int totalCombination = 0;
for(int[] row: rowPerms){
int i=0;
int[][] tmpArr = createCopy(digitsRemaining);
for(;i<row.length;i++){
if(row[i]==0){
if(tmpArr[i][0] - 1 >= 0){
tmpArr[i][0] -= 1;
}else
break;
}else{
if(tmpArr[i][1] - 1 >= 0){
tmpArr[i][1] -= 1;
}else
break;
}
}
//If row permutation is successfully used for this level
//else try next permuation
if(i==row.length){
//If last row of matrix return 1
if(level == 1){
return 1;
}else{
int combinations = possibleCombinations(tmpArr, level-1);
arrangeFunction.put(getStringForDigitsRemaining(tmpArr), combinations);
totalCombination += combinations;
}
}
}
return totalCombination;
}
/**
* Creating deep copy of 2 dimensional array
* @param arr
* @return
*/
private int[][] createCopy(int[][] arr){
int[][] newArr = new int[arr.length][arr[0].length];
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr[0].length;j++){
newArr[i][j] = arr[i][j];
}
}
return newArr;
}
private void printRow(int[] row){
for(int i: row)
System.out.print(i);
}
private String getStringForDigitsRemaining(int[][] digitsRemaining){
StringBuilder sb = new StringBuilder();
for(int i=0;i<digitsRemaining.length;i++){
sb.append(digitsRemaining[i][0]);
sb.append(digitsRemaining[i][1]);
}
return sb.toString();
}
/**
* Calculates x choose y
* @param x
* @param y
*/
private int combination(int x, int y){
if(x>0 && y>0 && x>y)
return factorial(x)/(factorial(y)*factorial(x-y));
else
return 0;
}
private int factorial(int x){
if(x==0)
return 1;
return x*factorial(x-1);
}
private void printAllCombination(){
for(int[] arr: rowPerms){
for(int i: arr)
System.out.print(i);
System.out.println();
}
}
}