2
\$\begingroup\$

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

}
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.