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);
}
}
