You are given a whole number amount of money (in rupees) and an array coins with the values of the coins you have. You have an unlimited number of coins of each value.
Return the number of different combinations of coins that add up to exactly amount. A combination does not care about order, so 1 + 2 and 2 + 1 are the same combination. If no combination works, return 0.
The answer is guaranteed to fit in a signed 32-bit integer.
Examples
Example 1:
Input: amount = 6, coins = [1,3,4]
Output: 4
Explanation: The combinations are 1x6, 3+1+1+1, 3+3 and 4+1+1. That is 4 ways.
Example 2:
Input: amount = 7, coins = [2,4]
Output: 0
Explanation: Coins of 2 and 4 can only make even amounts, so 7 is not possible.
Example 3:
Input: amount = 0, coins = [5]
Output: 1
Explanation: To make 0 you use no coins. That counts as exactly one way.