import java.util.*;
 
class Ideone{
 
	private static int INT_MAX = 100000;
 
	public static void main(String[] args){
		int a[] = {1,7,4,11};
 
		//Input: n integers range (0 to k) A1, A2....An
		//Goal: Partition into two subsets S1&S2, minimize |Sum(s1) - Sum(s2)| 
		//
		//P[i,j]= 1 if some subset of {A1...Ai} has a sum of j, P[i-1, j] ==1 || P[i-1, j-Ai]==1
		//      = 0 otherwise
		//
 
		//Calculate sum of all integers of the array S
		int sum = 0;
		int n = a.length;
		for(int x : a){
			sum += x;
		}
		System.out.println("Total sum of the array => "+ sum);
 
		boolean[][] partition = new boolean[n+1][sum+1];
 
 		//If sum is zero, answer is true
 		for(int i=0; i<n+1; i++){
 			partition[i][0] = true;
 		}
 
		//If elements to include are zero, we cannot make sum. so it is false
		for(int i=0; i<sum+1;i++){
			partition[0][i] = false;
		}
 
		//File the subset table
		for(int i=1; i<n+1; i++){
			for(int j=1; j<sum+1; j++){
				if(partition[i-1][j] || (j>=a[i-1] && partition[i-1][j-a[i-1]])){
					partition[i][j] = true;
				}else{
					partition[i][j]= false;
				}
			}
		}
 
	   int min = INT_MAX;
	   for(int i=0; i<n+1; i++){
	   		for(int j=0; j<sum+1; j++){
	   			if(partition[i][j] && min > sum-j){
	   				min = sum-j;
	   			}
	   		}
	   }
 
	   System.out.println("Partition sum with min diff => "+ min);
	}
}