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

        for (int i = 1; i &lt; m.length; i++) {
            for (int j = 1; j &lt; m[0].length; j++) {
                m[i][j] = m[i][j - 1];
                if (i &gt;= 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.

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.