Given an array of non-negative integers, check whether there are two equals sum subset exist.
Let isSubsetSum(int[] array, int n, int sum) is a recursive function which is used to check whether there are two subsets with the sum equal to sum.
The isSubsetSum problem can be divided into two subproblems
a) Include the last element, recursive call isSubsetSum for n = n-1, sum = sum – array[n-1]
b) Exclude the last element, recursive call isSubsetSum for n = n-1.
If any of recursive call of sub problems return true, then return true.
isSubsetSum (array, n, sum) = isSubsetSum(array, n-1, sum) ||
isSubsetSum(array, n-1, sum-array[n-1])
Base Cases
isSubsetSum(array, n, sum) = true, if sum == 0
isSubsetSum(array, n, sum) = false, if sum > 0 and n == 0.
/**
* Checks whether the array contains two subsets of equals sum.
* @author rajesh.dixit
*/
public class SubsetSum {
/** This static global variable is used to count the iterations. */
private static int counter = 0;
private static boolean isSubsetSum(int[] array, int n, long sum) {
counter++;
/** Base case : Condition to break the recursion. */
if (sum == 0) {
return true;
}
/** To avoid ArrayIndexOutOfBoundExeption. */
if (n == 0 && sum != 0) {
return false;
}
/**
* Checking whether the sum can be obtained,
* (a) Including the current element.
* (b) Excluding the current element.
*/
return isSubsetSum(array, n - 1, sum) ||
isSubsetSum(array, n - 1, sum - array[n - 1]);
}
/**
* Checks prerequisites and calculate the data for the
* recursive method.
* @param array
* @return true or false based on the condition.
*/
private static boolean isEqualSumSubsetExits(int[] array) {
long sum = 0;
for (int value : array) {
sum += value;
}
/**
* Sum of the array is odd so equals two subset cannot
* find exits here.
*/
if (sum % 2 != 0) {
return false;
}
sum = sum / 2;
return isSubsetSum(array, array.length, sum);
}
/** Driver method. */
public static void main(String[] args) {
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 };
boolean exist = isEqualSumSubsetExits(array);
String existStr = (exist ? "" : "not");
System.out.printf("Equal sum subset%s exits ", existStr);
System.out.println();
System.out.printf("Total %d iteration to identify it", counter);
}
}
Worst case time complexity of the above solution is exponential.
Dynamic programming approach
We can solve the problem in Pseudo-polynomial time. We create a 2D array ‘dp’ and the value of dp[i][j] will be true if there is a subset of array[0..j-1] with the sum equal to j, otherwise false. Finally, we will return dp[sum][n].
package com.algorithm;
/**
* Checks whether the array contains two subsets of equal sum.
*
* @author rajesh.dixit
*/
public class SubsetSumDP {
private static boolean isSubsetSum(int[] array, int sum) {
int row = array.length + 1;
int col = sum + 1;
boolean[][] dp = new boolean[row][col];
for (int i = 1; i < row; i++) {
int element = array[i - 1];
for (int j = 1; j < col; j++) {
if (element == j) {
dp[i][j] = true;
} else if (dp[i - 1][j]) {
dp[i][j] = true;
if ((j + element) < col) {
dp[i][j + element] = true;
}
}
}
}
/* for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
System.out.print((dp[i][j] ? "T" : "F") + " ");
}
System.out.println();
}*/
return dp[row - 1][col - 1];
}
/**
* Checks prerequisites and calculate the data for the recursive method.
*
* @param array
* @return true or false based on the condition.
*/
private static boolean isEqualSumSubsetExits(int[] array) {
int sum = 0;
for (int value : array) {
sum += value;
}
/** Sum of the array is odd so equals two subset cannot find exits here. */
if (sum % 2 != 0) {
return false;
}
sum = sum / 2;
return isSubsetSum(array, sum);
}
/** Driver method. */
public static void main(String[] args) {
int[] array = { 1, 3, 4, 7, 8, 1 };
boolean exits = isEqualSumSubsetExits(array);
System.out.printf("Equal sum subset%s exits ", (exits ? "" : "not"));
}
}
No comments:
Post a Comment