aloalgoCoin Change - Number of Coin Combinations
Medium
You are given an integer array coins representing available coin denominations and an integer amount representing a target total amount of money.
Your task is to calculate the number of distinct combinations of coins that sum up to the amount.
You may assume that:
- You have an infinite number of each kind of coin.
Return the total number of distinct combinations. If no combination of coins can sum up to the amount, return 0.
Example 1
Inputs
amount = 11
coins = [1, 5, 10, 25]
Output
4
Explanation:
The amount 11 can be made in three ways
- one 10-coin and one 1-coin
- with two 5-coins and one 1-coin
- with one 5-coins and six 1-coin
- eleven 1-coins.
Example 2
Inputs
amount = 3
coins = [5, 10, 25]
Output
0
Explanation:
The amount 3 cannot be made with the given coin denominations.
Example 3
Inputs
amount = 0
coins = [1, 5, 10, 25]
Output
1
Explanation:
There is one way to make the amount 0: by using no coins.
Inputs
amount = 11
coins = [1, 5, 10, 25]
Output
4