Number of ways of selecting the numbers

Suppose i am given an array and a sum.I am asked to find the number of ways in which i can select the numbers from the given list(one number can be used any number of times) so that i can achieve the sum by adding all the selected numbers from the array
Eg: arr[]={2,3} and sum=6 then we can select the numbers like {2,2,2},{3,3} and here i guess the count is 2…}
I felt that this is a question related to DP.I have just heard of DP.I know nothing on DP.I am just a newbie.Can you please explain it?
I tried to Brute Force it…And the result was a failure…

This is a type of subset sum problem which is NP-Complete. So for unrestricted range of numbers, you can’t tell the number of ways to do so.

But if there is limit on sum of numbers, then `O(NS)` dynamic programming algorithm exist, where `S` is sum of numbers and `N` is the count of numbers.

Lets calculate `dp[i][j]`, which is possible number of ways of getting sum `j`, when initial `i` elements are used. So we calculate the new sum when i+1th element is used.

`dp[i][sum] += dp[i-1][sum - a[i-1]];` So if we want to get sum `j` when including ith number, then find ways to get sum `j-a[i-1]` using previous `i-1` numbers and add a[i] to get sum = j. So do this for all values of `j`.

Let a[] is the array containing all the numbers.

``````for(i = 1;i <= N;i++)
{
for(sum = 0;sum <= S;sum++)
{
dp[i][sum] += dp[i-1][sum - a[i-1]];
dp[i][sum] += dp[i-1][sum] //when the number a[i] is not added

}
}
``````

Let given sum to find is D.
In the end dp[N][D] gives the ways to find sum D.

3 Likes