Subset sum problem – Dynamic Programming

Given a set (or multiset) of integers, is there a non-empty subset whose sum is zero?

For example, given the set {−7, −3, −2, 5, 8}, the answer is yes because the subset {−3, −2, 5} sums to zero. The problem is NP-complete. A variant of this problem could be formulated as –

Given a set (or multiset) of integers, is there a subset whose sum is equal to a given sum?

For example A = [3, 34, 4, 12, 5, 2] and sum = 26 then subsum(A, 26) = true as there is a subset {3, 4, 12, 5, 2} that sums up to 26.

Note that, this is not zero-sum subarray problem which find a contagious subarray that sums up to zero. Checkout my previous post for solution to this problem.

We observe that we can solve this problem by solving the subproblem of finding solution for a lower sum. That is we can use a DP approach. We usually use DP when –

1. We can formulate the solution combining solutions of smaller subproblem, and.
2. There are overlapping subproblems.

Optimal Substructure
We can see that if we can find the whether a subset S={s1, s2,…,sm} exists such that sum of elements equals to sum n EITHER by excluding sm and using the solution of a smaller subset S = {s1. s2, …, sm-1} that sums up to n OR by including sm and using the solution of a smaller subset S = {s1. s2, …, sm-1} that sums up to n-sm.

let, ss(S, n, m) be the number of solutions of making n using first m numbers S={s1, s2,…,sm}. The we can write the following recursive formula,

ss(S, n, m) = ss(S, n, m-1) OR ss(S, n-sm, m-1).

It is now clear that subset sum has a optimal substructure.

Overlapping Subproblems
Lets S = {0, 1, 2, 3, 5}, m=5 and sum, n = 5
If we write down the pictorial representation of the above recursion the we can see from the following figure that subproblems (such as ss({0,1,2},2,3) ) are getting repeated. That’s is we have overlapping subproblems and so we can use a table to store previous computation of solution to a sub problem.

                           ss({0,1,2,3,5},5,5)                     
                           /                \
                         /                   \              
          ss({0,1,2,3},0,4)               ss({0,1,2,3},5,4)
                                             /         \
                                            /           \
                                  ss({0,1,2},5,3)     ss({0,1,2}, 2, 3)
                                       /    \                /        \
                                      /      \              /          \
                          ss({0,1},5,2) ss({0,1},3,2) ss({0,1},2,2) ss({0, 1}, 0, 2)
                               / \         / \        /     \    
                              /   \       /   \      /       \ 
                         .  .     .   .     .       .. ..      .... 


Below is a O(nm) solution for the coin sum problem using DP. 

public static boolean isSubSetSum(final int[] set, final int sum) {
    final int m = set.length;
    final boolean[][] ssTable = new boolean[sum + 1][m + 1];

    // base cases: if m == 0 then no solution for any sum
    for (int i = 0; i <= sum; i++) {
        ssTable[i][0] = false;
    }
    // base case: if sum = 0 then there is only one solution for any input set: just take none of each of the items.
    for (int j = 0; j <= m; j++) {
        ssTable[0][j] = true;
    }

    for (int i = 1; i <= sum; i++) {
        for (int j = 1; j <= m; j++) {
            // solutions excluding last element i.e. set[j-1]
            final boolean s1 = ssTable[i][j - 1];
            // solutions including last element i.e. set[j-1]
            final boolean s2 = (i - set[j - 1]) >= 0 ? ssTable[i - set[j - 1]][j - 1] : false;

            ssTable[i][j] = s1 || s2;
        }
    }

    return ssTable[sum][m];
}