import java.util.*;
class Ideone{
public static void main
(String[] args
){ int set[] = {3,5,4,6,1,7}; //{3,4,6}, {1,7,5}
int n = set.length;
int totalSum = 0;
for(int x:set) totalSum+=x;
if(totalSum%2 == 1) {
System.
out.
println("Equal partition not possible as summ is odd"); return;
}
//This code has complexity of O(N * SUM) and uses O(N * SUM) extra space.
int sum = totalSum/2; //Find out whether sum can be formed or not
boolean[][] partitionSum = new boolean[n+1][sum+1];
//If sum is zero, we don't require to include any element. So default value will be true
for(int i=0; i<n+1; i++){
partitionSum[i][0] = true;
}
//If set is empty, we can't get sum without including any element
for(int i=0; i<sum+1; i++){
partitionSum[0][i] = false;
}
for(int i=1; i<n+1; i++){
for(int j=1; j<sum+1; j++){
if(partitionSum[i-1][j] || (j >=set[i-1] && partitionSum[i-1][j-set[i-1]])){
partitionSum[i][j] = true;
}
}
}
if(partitionSum[n][sum]){
System.
out.
println("Equal partition possible"); }else{
System.
out.
println("Equal partition not possible with given input set"); }
}
}
aW1wb3J0IGphdmEudXRpbC4qOwoKY2xhc3MgSWRlb25lewoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncyl7CgkJIGludCBzZXRbXSA9IHszLDUsNCw2LDEsN307IC8vezMsNCw2fSwgezEsNyw1fQoJCSBpbnQgbiA9IHNldC5sZW5ndGg7CgoJCSBpbnQgdG90YWxTdW0gPSAwOwoJCSBmb3IoaW50IHg6c2V0KSB0b3RhbFN1bSs9eDsJCgoJCSBpZih0b3RhbFN1bSUyID09IDEpIHsKCQkgCSBTeXN0ZW0ub3V0LnByaW50bG4oIkVxdWFsIHBhcnRpdGlvbiBub3QgcG9zc2libGUgYXMgc3VtbSBpcyBvZGQiKTsKCQkgCSByZXR1cm47CgkJIH0KCgkJLy9UaGlzIGNvZGUgaGFzIGNvbXBsZXhpdHkgb2YgTyhOICogU1VNKSBhbmQgdXNlcyBPKE4gKiBTVU0pIGV4dHJhIHNwYWNlLgoJCSBpbnQgc3VtID0gdG90YWxTdW0vMjsgLy9GaW5kIG91dCB3aGV0aGVyIHN1bSBjYW4gYmUgZm9ybWVkIG9yIG5vdCAKCQkgYm9vbGVhbltdW10gcGFydGl0aW9uU3VtID0gbmV3IGJvb2xlYW5bbisxXVtzdW0rMV07CgkJCgkJIC8vSWYgc3VtIGlzIHplcm8sIHdlIGRvbid0IHJlcXVpcmUgdG8gaW5jbHVkZSBhbnkgZWxlbWVudC4gU28gZGVmYXVsdCB2YWx1ZSB3aWxsIGJlIHRydWUKCQkgZm9yKGludCBpPTA7IGk8bisxOyBpKyspewoJCSAJcGFydGl0aW9uU3VtW2ldWzBdID0gdHJ1ZTsKCQkgfQoKCQkgLy9JZiBzZXQgaXMgZW1wdHksIHdlIGNhbid0IGdldCBzdW0gd2l0aG91dCBpbmNsdWRpbmcgYW55IGVsZW1lbnQKCQkgZm9yKGludCBpPTA7IGk8c3VtKzE7IGkrKyl7CgkJIAlwYXJ0aXRpb25TdW1bMF1baV0gPSBmYWxzZTsKCQkgfQoKCQkgZm9yKGludCBpPTE7IGk8bisxOyBpKyspewoJCSAJZm9yKGludCBqPTE7IGo8c3VtKzE7IGorKyl7CgkJIAkJaWYocGFydGl0aW9uU3VtW2ktMV1bal0gfHwgKGogPj1zZXRbaS0xXSAmJiBwYXJ0aXRpb25TdW1baS0xXVtqLXNldFtpLTFdXSkpewoJCSAJCQlwYXJ0aXRpb25TdW1baV1bal0gPSB0cnVlOwoJCSAJCX0KCQkgCX0KCQkgfQoKCQkgaWYocGFydGl0aW9uU3VtW25dW3N1bV0pewoJCSAJU3lzdGVtLm91dC5wcmludGxuKCJFcXVhbCBwYXJ0aXRpb24gcG9zc2libGUiKTsKCQkgfWVsc2V7CgkJIAlTeXN0ZW0ub3V0LnByaW50bG4oIkVxdWFsIHBhcnRpdGlvbiBub3QgcG9zc2libGUgd2l0aCBnaXZlbiBpbnB1dCBzZXQiKTsKCQkgfQoJfQp9Cg==