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…

Advance Thanks…

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+1^{th} element is used.

`dp[i][sum] += dp[i-1][sum - a[i-1]];`

So if we want to get sum `j`

when including i^{th} 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.