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


Comments

Post a Comment

Popular posts from this blog

Typical Programs in C/C++

  Sum of two large numbers Difficulty Level :   Medium   Last Updated :  04 Jun, 2019 Given two numbers as strings. The numbers may be very large (may not fit in long long int), the task is to find sum of these two numbers. Examples: Input : str1 = "3333311111111111", str2 = "44422222221111" Output : 3377733333332222 Input : str1 = "7777555511111111", str2 = "3332222221111" Output : 7780887733332222 The idea is based on school mathematics. We traverse both strings from end, one by one add digits and keep track of carry. To simplify the process, we do following: 1) Reverse both strings. 2) Keep adding digits one by one from 0’th index (in reversed strings) to end of smaller string, append the sum % 10 to end of result and keep track of carry as sum/10. 3) Finally reverse the result. // C++ program to find sum of two large numbers. #include<bits/stdc++.h> using namespace std;     // Function for finding sum of la...
Read more

Which data structure is used in redo-undo feature?

Explanation:  Stack data structure is most suitable to implement redo-undo feature. This is because the stack is implemented with LIFO(last in first out) order which is equivalent to redo-undo feature i.e. the last re-do is undo first. Consider a situation where a client receives packets from a server. There may be differences in speed of the client and the server. Which data structure is best suited for synchronization? (A)  Circular Linked List (B)  Queue (C)  Stack (D)  Priority Queue Answer:   (B) Explanation:  Since packets need to be processed in First In First Out order, a queue can be used for synchronization. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set. o Delection of the smallest element o Insertion of an element if it is not already present in the set Which of the following data structur...
Read more
Image
  C Program to Check if a Given String is Palindrome // A function to check if a string str is palindrome void isPalindrome( char str[]) {      // Start from leftmost and rightmost corners of str      int l = 0;      int h = strlen (str) - 1;          // Keep comparing characters while they are same      while (h > l)      {          if (str[l++] != str[h--])          {              printf ( "%s is Not Palindrome" , str);              return ;          }      }      printf ( "%s is palindrome" , str); }     // Driver program to test above function int main() {...
Read more