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.
Sreekumar (KJ) has been a hobby programmer from school days. Codemarvels is his personal blog from the year 2010, where he writes about technology, philosophy, society and a bit about physics.
He now runs a conversational AI company – DheeYantra – focusing his efforts to help businesses improve operational efficiency using digital employees powered by AI.