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-
[cpp]
//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];
}
[/cpp]
Note-
This algorithm works only for positive numbers.
