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
); }
}
aW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgSWRlb25lewoKCXByaXZhdGUgc3RhdGljIGludCBJTlRfTUFYID0gMTAwMDAwOwoKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpewoJCWludCBhW10gPSB7MSw3LDQsMTF9OwoJCQoJCS8vSW5wdXQ6IG4gaW50ZWdlcnMgcmFuZ2UgKDAgdG8gaykgQTEsIEEyLi4uLkFuCgkJLy9Hb2FsOiBQYXJ0aXRpb24gaW50byB0d28gc3Vic2V0cyBTMSZTMiwgbWluaW1pemUgfFN1bShzMSkgLSBTdW0oczIpfCAKCQkvLwoJCS8vUFtpLGpdPSAxIGlmIHNvbWUgc3Vic2V0IG9mIHtBMS4uLkFpfSBoYXMgYSBzdW0gb2YgaiwgUFtpLTEsIGpdID09MSB8fCBQW2ktMSwgai1BaV09PTEKCQkvLyAgICAgID0gMCBvdGhlcndpc2UKCQkvLwoJCQoJCS8vQ2FsY3VsYXRlIHN1bSBvZiBhbGwgaW50ZWdlcnMgb2YgdGhlIGFycmF5IFMKCQlpbnQgc3VtID0gMDsKCQlpbnQgbiA9IGEubGVuZ3RoOwoJCWZvcihpbnQgeCA6IGEpewoJCQlzdW0gKz0geDsKCQl9CgkJU3lzdGVtLm91dC5wcmludGxuKCJUb3RhbCBzdW0gb2YgdGhlIGFycmF5ID0+ICIrIHN1bSk7CgoJCWJvb2xlYW5bXVtdIHBhcnRpdGlvbiA9IG5ldyBib29sZWFuW24rMV1bc3VtKzFdOwoKIAkJLy9JZiBzdW0gaXMgemVybywgYW5zd2VyIGlzIHRydWUKIAkJZm9yKGludCBpPTA7IGk8bisxOyBpKyspewogCQkJcGFydGl0aW9uW2ldWzBdID0gdHJ1ZTsKIAkJfQoKCQkvL0lmIGVsZW1lbnRzIHRvIGluY2x1ZGUgYXJlIHplcm8sIHdlIGNhbm5vdCBtYWtlIHN1bS4gc28gaXQgaXMgZmFsc2UKCQlmb3IoaW50IGk9MDsgaTxzdW0rMTtpKyspewoJCQlwYXJ0aXRpb25bMF1baV0gPSBmYWxzZTsKCQl9CgkJCgkJLy9GaWxlIHRoZSBzdWJzZXQgdGFibGUKCQlmb3IoaW50IGk9MTsgaTxuKzE7IGkrKyl7CgkJCWZvcihpbnQgaj0xOyBqPHN1bSsxOyBqKyspewoJCQkJaWYocGFydGl0aW9uW2ktMV1bal0gfHwgKGo+PWFbaS0xXSAmJiBwYXJ0aXRpb25baS0xXVtqLWFbaS0xXV0pKXsKCQkJCQlwYXJ0aXRpb25baV1bal0gPSB0cnVlOwoJCQkJfWVsc2V7CgkJCQkJcGFydGl0aW9uW2ldW2pdPSBmYWxzZTsKCQkJCX0KCQkJfQoJCX0KCgkgICBpbnQgbWluID0gSU5UX01BWDsKCSAgIGZvcihpbnQgaT0wOyBpPG4rMTsgaSsrKXsKCSAgIAkJZm9yKGludCBqPTA7IGo8c3VtKzE7IGorKyl7CgkgICAJCQlpZihwYXJ0aXRpb25baV1bal0gJiYgbWluID4gc3VtLWopewoJICAgCQkJCW1pbiA9IHN1bS1qOwoJICAgCQkJfQoJICAgCQl9CgkgICB9CgoJICAgU3lzdGVtLm91dC5wcmludGxuKCJQYXJ0aXRpb24gc3VtIHdpdGggbWluIGRpZmYgPT4gIisgbWluKTsKCX0KfQo=