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.
Example:

Input:  set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.

We can solve the problem in Pseudo-polynomial time using Dynamic programming. 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]

// A Dynamic Programming solution for subset sum problem

#include <stdio.h>

   

// Returns true if there is a subset of set[] with sun equal to given sum

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[n+1][sum+1];

   

    // If sum is 0, then answer is true

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

      subset[i][0] = true;

   

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

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

      subset[0][i] = false;

   

     // Fill the subset table in botton up manner

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

     {

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

       {

         if(j<set[i-1])

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

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

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

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

       }

     }

   

     /*   // uncomment this code to print table

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

     {

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

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

       printf("\n");

     }*/

   

     return subset[n][sum];

}

   

// Driver program to test above function

int main()

{

  int set[] = {3, 34, 4, 12, 5, 2};

  int sum = 9;

  int n = sizeof(set)/sizeof(set[0]);

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

     printf("Found a subset with given sum");

  else

     printf("No subset with given sum");

  return 0;

}

// A Dynamic Programming solution for subset // sum problem class GFG {            // Returns true if there is a subset of      // set[] with sun equal to given sum     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++)             System.out.println (subset[i][j]);         } */                return subset[sum][n];     }        /* Driver program to test above function */     public static void main (String args[])     {         int set[] = {3, 34, 4, 12, 5, 2};         int sum = 9;         int n = set.length;         if (isSubsetSum(set, n, sum) == true)             System.out.println("Found a subset"                           + " with given sum");         else             System.out.println("No subset with"                                + " given sum");     } }    /* This code is contributed by Rajat Mishra */

Output:

Found a subset with given sum

Time complexity of the above solution is O(sum*n).

# A Dynamic Programming solution for subset sum problem # Returns true if there is a subset of  # set[] with sun equal to given sum     # Returns true if there is a subset of set[]  # with sun equal to given sum def isSubsetSum(set,n,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     subset=([[False for i in range(sum+1)]              for i in range(n+1)])            # If sum is 0, then answer is true      for i in range(n+1):         subset[i][0] = True                    # If sum is not 0 and set is empty,          # then answer is false          for i in range(1,sum+1):             subset[0][i]=False                        # Fill the subset table in botton up manner         for i in range(1,n+1):             for j in range(1,sum+1):                 if j<set[i-1]:                     subset[i][j] = subset[i-1][j]                 if j>=set[i-1]:                     subset[i][j] = (subset[i-1][j] or                                     subset[i - 1][j-set[i-1]])                # uncomment this code to print table          # for i in range(n+1):         # for j in range(sum+1):         #     print (subset[i][j],end=" ")         # print()     return subset[n][sum]            # Driver program to test above function if __name__=='__main__':     set = [3, 34, 4, 12, 5, 2]     sum = 9     n =len(set)     if (isSubsetSum(set, n, sum) == True):         print("Found a subset with given sum")     else:         print("No subset with given sum")            # This code is contributed by  # sahil shelangia.

Output:

Found a subset with given sum

Time complexity of the above solution is O(sum*n).

https://www.youtube.com/watch?v=dJmyfFC3-3A