Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum. On similar lines, 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.
Complexity:
- \$O(n \times m)\,ドル \$n\$ is the array length and \$m\$ is the sum.
Looking for code-review, optimizations and best practices.
public final class SubSetSum {
private SubSetSum() {}
/**
* 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.
*
* A negative value in array would case unpredicatable results.
*
* 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.
*
* @param a the input array
* @return true if array can be partitioned into subsets, else false.
*/
public static boolean canPartition(int[] a) {
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum = sum + a[i];
}
if ((sum % 2) == 1) return false;
return subsetSum(a, sum % 2);
}
/**
* Given a set of non-negative integers, and a value sum, determine if there is a subset
* of the given set with sum equal to given sum.
*
* Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
* Output: True //There is a subset (4, 5) with sum 9.
*
* A negative value in array would case unpredicatable results.
*
* @param a the input array
* @param sum the input sum
* @return true if some subset of elements add up to the sum.
*/
public static boolean subsetSum(int[] a, int sum) {
boolean[][] m = new boolean[sum + 1][a.length + 1];
for (int j = 0; j < m[0].length; j++) {
m[0][j] = true;
}
for (int i = 1; i < m.length; i++) {
for (int j = 1; j < m[0].length; j++) {
m[i][j] = m[i][j - 1];
if (i >= a[j - 1]) {
m[i][j] = m[i][j - 1] || m[i - a[j-1]][j-1];
}
}
}
return m[sum][a.length];
}
}
public class SubSetSumTest {
@Test
public void testCanPartition() {
int[] a1 = {1, 2, 3, 4};
assertTrue(SubSetSum.canPartition(a1));
int[] a2 = {1, 2, 3, 4, 5};
assertFalse(SubSetSum.canPartition(a2));
int[] a3 = {1, 2, 3, 4, 5, 6};
assertFalse(SubSetSum.canPartition(a3));
int[] a4 = {1, 2, 3, 4, 5, 7};
assertTrue(SubSetSum.canPartition(a4));
}
@Test
public void testSubsetSum() {
int[] a = {1, 3, 8, 9};
assertTrue(SubSetSum.subsetSum(a, 1));
assertFalse(SubSetSum.subsetSum(a, 2));
assertTrue(SubSetSum.subsetSum(a, 3));
assertTrue(SubSetSum.subsetSum(a, 4));
assertFalse(SubSetSum.subsetSum(a, 5));
assertFalse(SubSetSum.subsetSum(a, 6));
assertFalse(SubSetSum.subsetSum(a, 7));
assertTrue(SubSetSum.subsetSum(a, 8));
assertTrue(SubSetSum.subsetSum(a, 9));
assertTrue(SubSetSum.subsetSum(a, 10));
assertTrue(SubSetSum.subsetSum(a, 11));
assertTrue(SubSetSum.subsetSum(a, 12));
assertTrue(SubSetSum.subsetSum(a, 12));
assertTrue(SubSetSum.subsetSum(a, 13));
assertFalse(SubSetSum.subsetSum(a, 14));
assertFalse(SubSetSum.subsetSum(a, 15));
assertFalse(SubSetSum.subsetSum(a, 16));
assertTrue(SubSetSum.subsetSum(a, 17));
assertTrue(SubSetSum.subsetSum(a, 18));
assertFalse(SubSetSum.subsetSum(a, 19));
assertTrue(SubSetSum.subsetSum(a, 20));
assertTrue(SubSetSum.subsetSum(a, 21));
}
}
1 Answer 1
This solution is very dependant on m for the space complexity.
I worry that, with the inputs:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2000000000]
and the target sum 2000000002 that your program will run out of memory (it will do: boolean[][] m = new boolean[sum + 1][a.length + 1]; which will create an array of about 20GB or more.... actually, it will be worse... about 80GB.
Additionally, you have labelled this as a 'dynamic programming' problem, but there is no recursion here, and no memoization/re-use....
In a review, I would challenge this solution's scalability, and assumptions.