Subset Sum Problem

Given a set of positive integers and a value sum,the task is to find if there is a subset with sum equal to the given value.

Example-

Given set of numbers- {3,34,4,12,5,2}

Sum=9.

The output will be ‘True’ because 4+5=9.

Algorithm-

The problem can be divided into two sub-problems-

1.By including the last element.
2.By excluding the last element.

Recursive Solution-

subsum(set, n, sum) = subsum(set, n-1, sum)  //excluding the last element
                      || subsum(arr, n-1, sum-set[n-1]) //including the last element

Base Cases:

subsum(set, n, sum) = false, if sum > 0 and n == 0
subsum(set, n, sum) = true, if sum == 0 

Code-

The above algorithm has exponential time complexity which can be converted to code having polynomial complexity using dynamic programming that is storing the intermediate results.


// Returns true if there is a subset of set[] with sum 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[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];
}


Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

43,751 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>