Partition to two subsets

 Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.

Examples

arr[] = {1, 5, 11, 5}
Output: true
The array can be partitioned as {1, 5, 5} and {11}

arr[] = {1, 5, 3}

Output: false

The array cannot be partitioned into equal sum sets.

 

Following are the two main steps to solve this problem:

1) Calculate sum of the array. If sum is odd, there cannot be two subsets with equal sum, so return false.

2) If sum of array elements is even, calculate sum/2 and find a subset of array with sum equal to sum/2.

The first step is simple. The second step is crucial, it can be solved either using recursion or Dynamic Programming.

public static boolean subSetSum(int[] a, int n, int sum) {

if(sum == 0) {

return true;

}

if(n == 0 && sum != 0) {

return false;

}

if(a[n]>sum) {

subSetSum(a, n-1, sum);

}

return subSetSum(a, n-1, sum-a[n]) || subSetSum(a, n-1, sum);

}

public static boolean partitionTwoSubsets(int[] a) {

int totalSum = 0;

for(int i=0; i<a.length; i++) {

totalSum += a[i];

}

if(totalSum % 2 != 0) {

return false;

}

else {

return subSetSum(a, a.length-1, totalSum/2);

}

}