Number of ways of selecting the numbers

general
,
1

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…:frowning:
Advance Thanks…:slight_smile:

2

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.

1 Like