# Number of Ways

Posted: 31 Dec, 2020
Difficulty: Moderate

## PROBLEM STATEMENT

#### Consider a game in which players can choose any of the three coins => 3 or 5 or 10 in a move. There is an infinite supply of all the three types of coins. Given a total amount ‘N’, find the distinct combinations which sums up to 'N'.

##### Note :
``````3,5 and 5,3 are not distinct combinations.
``````

#### Input format:

``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and only line of each test case contains an integer ‘N’ , the total amount.
``````

#### Output format:

``````For each test case, return the number of distinct combinations to reach the total amount is printed.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 10
1 <= N <= 5 * 10^4

Time Limit: 1 sec
`````` Approach 1

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.