Dynamic Programming - Subset Sum Problem

Related:
Subset Sum Problem - DP
LeetCode 39 - Combination Sum
LeetCode 40 - Combination Sum II
Leetcode 216 Combination Sum III
LeetCode 377 - Combination Sum IV
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.

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])

We create a boolean 2D table subset[][] and fill it in bottom up manner. The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false. Finally, we return subset[sum][n]

Base Cases:
SubsetSum(arrA, n, S)= false, if sum > 0 and n == 0
SubsetSum(arrA, n, S)= true, if sum == 0 (return empty set)
Rest Cases
SubsetSum(arrA, n, S) = SubsetSum(arrA, n-1, S)|| SubsetSum(arrA, n-1, S-arrA[n-1])

   static boolean 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

        boolean subset[][] = new boolean[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];

    }

https://github.com/nastra/algorithms-java/blob/master/src/main/java/com/nastra/algorithms/dp/SubsetSum.java
public static boolean isSubsetSum(int[] s, int n, int sum) {
if (sum == 0) {
return true;
}
if (n <= 0 && sum != 0) {
return false;
}

// include the last element in the search - exclude last element from search
return isSubsetSum(s, n - 1, sum) || isSubsetSum(s, n - 1, sum - s[n - 1]);
}
public static boolean isSubsetSumDP(int[] s, int n, int sum) {
boolean[][] dp = new boolean[n + 1][sum + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
for (int i = 1; i <= sum; i++) {
dp[0][i] = false;
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= s[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j - s[i - 1]];
}
}
}

return dp[n][sum];
}
EPI Problem: Test if a tie is possible
TiesElection.java

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

X. Recursion

    static boolean isSubsetSum(int set[], int n, int sum)

    {

       // Base Cases

       if (sum == 0)

         return true;

       if (n == 0 && sum != 0)

         return false;

      

       // If last element is greater than sum, then ignore it

       if (set[n-1] > sum)

         return isSubsetSum(set, n-1, sum);

      

       /* else, check if sum can be obtained by any of the following

          (a) including the last element

          (b) excluding the last element   */

       return isSubsetSum(set, n-1, sum) ||

                                   isSubsetSum(set, n-1, sum-set[n-1]);

    }

http://algorithms.tutorialhorizon.com/dynamic-programming-subset-sum-problem/
public static void find(int[] A, int currSum, int index, int sum,
int[] solution) {
if (currSum == sum) {
System.out.println("\nSum found");
for (int i = 0; i < solution.length; i++) {
if (solution[i] == 1) {
System.out.print("  " + A[i]);
}
}

} else if (index == A.length) {
return;
} else {
solution[index] = 1;// select the element
currSum += A[index];
find(A, currSum, index + 1, sum, solution);
currSum -= A[index];
solution[index] = 0;// do not select the element
find(A, currSum, index + 1, sum, solution);
}
return;
}

http://www.geeksforgeeks.org/subset-sum-divisible-m/

Given a set of non-negative distinct integers, and a value m, determine if there is a subset of the given set with sum divisible by m.
Input Constraints
Size of set i.e., n <= 1000000, m <= 1000

Examples:

Input : arr[] = {3, 1, 7, 5};
        m = 6;
Output : YES

In subset sum problem we check if given sum subset exist or not, here we need to find if there exist some subset with sum divisible by m or not. Seeing input constraint, it looks like typical DP solution will work in O(nm) time. But in tight time limits in competitive programming, the solution may work. Also auxiliary space is high for DP table, but here is catch.

If n > m there will always be a subset with sum divisible by m (which is easy to prove with pigeonhole principle). So we need to handle only cases of n <= m .

For n <= m we create a boolean DP table which will store the status of each value from 0 to m-1 which are possible subset sum (modulo m) which have been encountered so far.

Now we loop through each element of given array arr[], and we add (modulo m) j which have DP[j] = true and store all the such (j+arr[i])%m possible subset sum in a boolean array temp, and at the end of iteration over j, we update DP table with temp. Also we add arr[i] to DP ie.. DP[arr[i]%m] = true.

In the end if DP[0] is true then it means YES there exist a subset with sum which is divisible by m, else NO

Time Complexity : O(m^2)
Auxiliary Space : O(m)

bool modularSum(int arr[], int n, int m)

{

    if (n > m)

        return true;

    // This array will keep track of all

    // the possible sum (after modulo m)

    // which can be made using subsets of arr[]

    // initialising boolean array with all false

    bool DP[m];

    memset(DP, false, m);

    // we'll loop through all the elements of arr[]

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

    {

        // anytime we encounter a sum divisible

        // by m, we are done

        if (DP[0])

            return true;

        // To store all the new encountered sum (after

        // modulo). It is used to make sure that arr[i]

        // is added only to those entries for which DP[j]

        // was true before current iteration. 

        bool temp[m];

        memset(temp,false,m);

        // For each element of arr[], we loop through

        // all elements of DP table from 1 to m and

        // we add current element i. e., arr[i] to

        // all those elements which are true in DP

        // table

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

        {

            // if an element is true in DP table

            if (DP[j] == true)

            {

                if (DP[(j+arr[i]) % m] == false)

                    // We update it in temp and update

                    // to DP once loop of j is over

                    temp[(j+arr[i]) % m] = true;

            }

        }

        // Updating all the elements of temp

        // to DP table since iteration over

        // j is over

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

            if (temp[j])

                DP[j] = true;

        // Also since arr[i] is a single element

        // subset, arr[i]%m is one of the possible

        // sum

        DP[arr[i]%m] = true;

    }

    return DP[0];

}

http://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/

Given an array of integers and a sum, the task is to print all subsets of given array with sum equal to given sum.

Examples:

Input : arr[] = {2, 3, 5, 6, 8, 10}
        sum = 10
Output : 5 2 3
         2 8

we build a 2D array dp[][] such that dp[i][j] stores true if sum j is possible with array elements from 0 to i.
After filling dp[][], we recursively traverse it from dp[n-1][sum]. For cell being traversed, we store path before reaching it and consider two possibilities for the element.
1) Element is included in current path.
2) Element is not included in current path.

Whenever sum becomes 0, we stop the recursive calls and print current path.

void printSubsetsRec(int arr[], int i, int sum, vector<int>& p)

{

    // If we reached end and sum is non-zero. We print

    // p[] only if arr[0] is equal to sun OR dp[0][sum]

    // is true.

    if (i == 0 && sum != 0 && dp[0][sum])

    {

        p.push_back(arr[i]);

        display(p);

        return;

    }

    // If sum becomes 0

    if (i == 0 && sum == 0)

    {

        display(p);

        return;

    }

    // If given sum can be achieved after ignoring

    // current element.

    if (dp[i-1][sum])

    {

        // Create a new vector to store path

        vector<int> b = p;

        printSubsetsRec(arr, i-1, sum, b);

    }

    // If given sum can be achieved after considering

    // current element.

    if (sum >= arr[i] && dp[i-1][sum-arr[i]])

    {

        p.push_back(arr[i]);

        printSubsetsRec(arr, i-1, sum-arr[i], p);

    }

}

// Prints all subsets of arr[0..n-1] with sum 0.

void printAllSubsets(int arr[], int n, int sum)

{

    if (n == 0 || sum < 0)

       return;

    // Sum 0 can always be achieved with 0 elements

    dp = new bool*[n];

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

    {

        dp[i] = new bool[sum + 1];

        dp[i][0] = true;

    }

    // Sum arr[0] can be achieved with single element

    if (arr[0] <= sum)

       dp[0][arr[0]] = true;

    // Fill rest of the entries in dp[][]

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

        for (int j = 0; j < sum + 1; ++j)

            dp[i][j] = (arr[i] <= j) ? dp[i-1][j] ||

                                       dp[i-1][j-arr[i]]

                                     : dp[i - 1][j];

    if (dp[n-1][sum] == false)

    {

        printf("There are no subsets with sum %d\n", sum);

        return;

    }

    // Now recursively traverse dp[][] to find all

    // paths from dp[n-1][sum]

    vector<int> p;

    printSubsetsRec(arr, n-1, sum, p);

}

Read full article from Dynamic Programming - Subset Sum Problem