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

}