Subset Sum Problem | DP-25

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.

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(set, 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 Following is naive recursive implementation that simply follows the recursive structure mentioned above.

div class="responsive-tabs">

C++

 // A recursive solution for subset sum problem #include    // Returns true if there is a subset of set[] with sun equal to given sum bool 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]); }    // 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);   if (isSubsetSum(set, n, sum) == true)      printf("Found a subset with given sum");   else      printf("No subset with given sum");   return 0; }

Java

 // A recursive solution for subset sum // problem class GFG {            // Returns true if there is a subset     // of set[] with sum equal to given sum     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]);     }            /* 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 */

Python3

 # A recursive solution for subset sum # problem    # Returns true if there is a subset  # of set[] with sun equal to given sum def isSubsetSum(set,n, sum) :          # Base Cases     if (sum == 0) :         return True     if (n == 0 and 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) or isSubsetSum(set, n-1, sum-set[n-1])               # Driver program to test above function 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 Nikita Tiwari.

C#

 // A recursive solution for subset sum problem using System;    class GFG {     // Returns true if there is a subset of set[] with sum     // equal to given sum     static bool 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]);     }            // Driver program      public static void Main ()     {         int []set = {3, 34, 4, 12, 5, 2};         int sum = 9;         int n = set.Length;         if (isSubsetSum(set, n, sum) == true)             Console.WriteLine("Found a subset with given sum");         else             Console.WriteLine("No subset with given sum");     } }    // This code is contributed by Sam007

PHP

 \$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]); }    // Driver Code \$set = array(3, 34, 4, 12, 5, 2); \$sum = 9; \$n = 6;    if (isSubsetSum(\$set, \$n, \$sum) == true)     echo"Found a subset with given sum"; else     echo "No subset with given sum";        // This code is contributed by Anuj_67  ?>

Output:

Found a subset with given sum

The above solution may try all subsets of given set in worst case. Therefore time complexity of the above solution is exponential. The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).

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]

C++

 // A Dynamic Programming solution for subset sum problem #include     // 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] = true;         // If sum is not 0 and set is empty, then answer is false     for (int i = 1; i <= sum; i++)       subset[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] ||                                   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(" ");      }*/          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);   if (isSubsetSum(set, n, sum) == true)      printf("Found a subset with given sum");   else      printf("No subset with given sum");   return 0; } // This code is contributed by Arjun Tyagi.

Java

 // 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[i] = true;                // If sum is not 0 and set is empty,         // then answer is false         for (int i = 1; i <= sum; i++)             subset[i] = 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 */

Python3

 # 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] = True                    # If sum is not 0 and set is empty,          # then answer is false          for i in range(1,sum+1):             subset[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] 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.

C#

 // A Dynamic Programming solution for subset sum problem using System;    class GFG {     // Returns true if there is a subset      // of set[] with sun equal to given sum     static 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 = new bool[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 bottom 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];                                                            }         }                return subset[sum,n];     }            // Driver program      public static void Main ()     {         int []set = {3, 34, 4, 12, 5, 2};         int sum = 9;         int n = set.Length;         if (isSubsetSum(set, n, sum) == true)             Console.WriteLine("Found a subset with given sum");         else             Console.WriteLine("No subset with given sum");     } } // This code is contributed by Sam007

PHP

 = \$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 \$set = array(3, 34, 4, 12, 5, 2); \$sum = 9; \$n = count(\$set);    if (isSubsetSum(\$set, \$n, \$sum) == true)     echo "Found a subset with given sum"; else     echo "No subset with given sum";    // This code is contributed by anuj_67. ?>

Output:

Found a subset with given sum

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