Dynamic Programming - Subset Sum Problem

Dynamic Programming - Subset Sum Problem
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.  

Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum. n is the number of elements in set[].
The isSubsetSum problem can be divided into two subproblems
…a) Include the last element, recur for n = n-1, sum = sum – set[n-1]
…b) Exclude the last element, recur for n = n-1.
If any of the above the above subproblems return true, then return true.
Following is the recursive formula for isSubsetSum() problem.

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) ||                              isSubsetSum(arr, n-1, sum-set[n-1])  

Base Cases:  isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0  

isSubsetSum(set, n, sum) = true, if sum == 0 

-- Be careful about the detail:

dp[sum][index] means whether there is match between 0-j-1, not 0-j.

http://www.zrzahid.com/subset-sum-problem-dynamic-programming/

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

bool isSubsetSum(int set[], int n, int sum)

{

    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]

    //  with sum equal to i

    bool subset[sum+1][n+1];

    // If sum is 0, then answer is true

    for (int i = 0; i <= n; i++)

      subset[0][i] = true;

    // If sum is not 0 and set is empty, then answer is false

    for (int i = 1; i <= sum; i++)

      subset[i][0] = false;

     // Fill the subset table in botton up manner

     for (int i = 1; i <= sum; i++)

     {

       for (int j = 1; j <= n; j++)

       {

         subset[i][j] = subset[i][j-1];

         if (i >= set[j-1])

           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];

       }

     }

    /* // uncomment this code to print table

     for (int i = 0; i <= sum; i++)

     {

       for (int j = 0; j <= n; j++)

          printf ("%4d", subset[i][j]);

       printf("\n");

     } */

     return subset[sum][n];

}

Extension:
how many subsets there are in which subset sum is equal X?
How many subsets of A={1,2,3,…,10} have the property that the sum of their elements is ≥28?
Read full article from Dynamic Programming - Subset Sum Problem