Subset Sum Problem (Part II)

Given a set of numbers,our task is to find the number of subsets that sum to a particular value.

Example-

Set of numbers- {1,3,2,5,4,9}
Sum=9

Subsets that sum to 9-

{1,3,5}
{5,4}
{9}
{3,2,4}

Thus,number of subsets that sum to 9 = 4.

Algorithm-

The idea is to find the number of possible sums with the current number.And its true that,there is exactly one way to bring sum to 0. At the beginning,we have only one number. We start from our target and subtract that number.If it is possible to get a sum of that number,then add it to the array element corresponding to the current number.

Code-


//N is the number of elements,
//sum is the given value,
//numbers[] contains the elements

int GetmNumberOfSubsets()
    {
        int dp[1000];
        dp[0] = 1;
        int currentSum =0;

        for (int i = 0; i < N; i++)
        {
            currentSum += numbers[i];
            for (int j = std::min(sum, currentSum); j >= numbers[i]; j--)
                dp[j] += dp[j - numbers[i]];
        }

        return dp[sum];
    }

Note-

This algorithm works only for positive numbers.

Leave a Reply

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

*

* Copy This Password *

* Type Or Paste Password Here *

41,085 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>