Number of Ways

To count all possible distinct combinations to reach the total amount of ‘N’ using coins of 3,5 and 10, we can divide all solutions in two sets.

• Solutions that contain the ith type of coin.
• Solutions that do not contain the ith type of coin.

The total number of distinct combinations can be found using recursion.

Algorithm: 

• Recursive Function: 'COUNT_WAYS_HELPER'(coins, M, N), where ‘coins’ is the list of coins available, that is {3,5,10}, ‘M’ is the type of coin available (one out of 3, 5 and 10)  and ‘N’ is the total amount.
• Base conditions =>
• If ‘N’ becomes 0, return 1.
• If ‘N’ becomes negative, return 0.
• If ‘M’ becomes negative, return 0.
   
• There will be two cases :
• Find all combinations which include Mth type of coin in it and sums up to the total amount : countWaysHepler(coins, m, N-coins[m]).
• Find all combinations which does not include Mth type of coin in it and sums up to the total amount : 'COUNT_WAYS_HELPER'(coins, m-1, N)
• Return the sum of above two cases.

The idea is the same as the previous approach, but in the previous approach, many recursive calls were made again and again with the same parameters. 

In the below diagram, the two parameters are : (coins array, total amount).

It is very clear that there are overlapping subproblems. This can be eliminated by storing the value obtained from a particular call in a 2d array, called the 'TABLE_ARRAY'.

'MEMO'[i][j] stores the count of distinct combinations which sums up to ‘i’ and once includes the jth coin and once excluding the ith coin.

Algorithm: 

• Create a 'MEMO' array of size [N+1][3] and initialize all its values with -1.
• Recursive Function: 'COUNT_WAYS_HELPER'(COINS, M, N), where ‘COINS' is the list of coins available, that is {3,5,10}, ‘M’ is the type of coin available (one out of 3, 5, and 10)  and ‘N’ is the total amount.
• Base conditions =>
• If ‘N’ becomes 0, return 1.
• If ‘N’ becomes negative, return 0.
• If ‘M’ becomes negative, return 0.
• If, 'MEMO'[N][M] is not -1, return its value.
   
• There will be two cases :
• Find all combinations which include M'th type of coin in it and sums up the total amount: countWaysHepler('COINS', m, N-coins[m]).
• Find all combinations which do not include Mth type of coin in it and sum up to the total amount: 'COUNT_WAYS_HELPER'(COINS, M-1, N)
• Update the sum of the above two cases in 'MEMO'[N][M] and return its value.
• Return the value of 'MEMO'[N][2].

For every type of coin, go through all the amounts ‘j’ , such that 0 <= j <= N, and update the value of 'DP'[j] as 'DP'[j] = 'DP'[j] + 'DP'[j - value of current coin]. This will add the count of distinct combinations that sums up to ‘j’ and that includes the current type of coin. And 'DP'[j] already had some value which was the count of distinct combinations that sums up to ‘j’, but only includes the coin that has occurred before the current coin in the coins array. Thus, at this point, 'DP'[j] contains the count of distinct combinations that sums up to ‘j’ with and without including all the coins up to the current type of coin.

Algorithm: 

• Take a 'DP' array of size ‘N+1’ and initialize all its values with 0.
• 'DP'[0] = 1
• For every type of coin :
• Iterate over the 'DP' array for all ‘j’ (such that : value of current coin <= j <= N),  'DP'[j] = 'DP'[j] + 'DP'[j - value of current coin].
• Return the value of 'DP'[N] that is the count of distinct combinations that sums up to ‘N’.