COIN CHANGE PROBLEM- TOTAL NUMBER OF WAYS

 PROBLEM STATEMENT:

We are given an array of coins (containing the value of coins which we are allowed to use with infinity number of each type of coins) and a sum (simply a large note[Indian currency] in real life) .  We have to determine the number of ways to make change of the note( sum of coins taken equal to the given sum ).

QUICK POINTS:

1. We can use one coin infinite number of times, i.e. it is an unbounded knapsack.

2. It is similar to subset sum problem, considering that one coin can be used  unlimited number of times.

STEPS:

1.  We take n, sum, a[n] as the size of array, given sum ( large note ) and the array of coins as input respectively.

2. Now, we are taking a table dp[n+1][sum+1] to store the number of ways starting from zero sized array and zero given sum to n sized array and sum as the given sum.

3. To store the corresponding values, we are taking two loops, i corresponds to size of array and j corresponds to given sum.

4. Now, we can observe that if j==0 i.e. given sum=0, the only possible way to make change of the sum is 1 (not taking any coin) and if i==0 i.e. we are not given any coin, then the possible way to make change is zero as we cannot make change out of nothing. This cases can be taken as initialization to continue the filling of the table by top down approach.

5. Now, if any coin has a value greater than the note, then we cannot include that coin in our choice and we will simply exclude it and proceed to the next step.

6. If the value of a coin is less than the value of the note, we have two choice, either we will take it or we will it. If we can take it, then we can take it multiple number of times. This two choices will sum up to give the result, as we are here to determine the total number of ways.

CODE:

#include <bits/stdc++.h>

using namespace std;

int main()

{

   int n,sum;

    cin>>n>>sum;

    int a[n];

    for(int i=0;i<n;i++)

        cin>>a[i];

    int dp[n+1][sum+1];

    for(int i=0;i<n+1;i++)

    {

        for(int j=0;j<sum+1;j++)

        {

            if(j==0)

                dp[i][j]=1;

            else if(i==0)

                dp[i][j]=0;

            else if(a[i-1]<=j)

                dp[i][j]=dp[i][j-a[i-1]]+dp[i-1][j];

            else if(a[i-1]>j)

                dp[i][j]=dp[i-1][j];

        }

    }

    cout<<dp[n][sum];

    return 0;

}

INPUT:

5    6

1    2    3    4    5

OUTPUT:

10

The possible ways are

1+1+1+1+1+1

1+1+1+1+2

1+1+1+3

1+1+2+2

1+1+4

1+5

1+2+3

2+2+2

2+4

3+3