# Determine if subset in int array adds up to a given input integer

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.length; j++) {
m[j] = true;
}

for (int i = 1; i < m.length; i++) {
for (int j = 1; j < m.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));
}

}


This solution is very dependant on m for the space complexity.
[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.