Count how many distinct combinations of coins sum to a target amount, where each coin type can be used any number of times.
Problem
You are given an integer amount and an array coins containing distinct coin denominations. Each denomination may be used any number of times.
Return the number of distinct combinations that add up exactly to amount.
A combination counts only by the multiset of coin values used, not by the order in which they are chosen. For example, using 1 + 2 is the same combination as 2 + 1.
If no combination can form the target amount, return 0.
Notes
- You may use unlimited copies of each coin denomination.
- Different orders of the same coins are not considered different combinations.
Input Format
coins: an array of positive integers representing coin denominationsamount: a non-negative integer target sum
Output Format
- Return an integer: the number of distinct combinations that make up
amount
Constraints
1 <= coins.length1 <= coins[i]amount >= 0- Coin denominations are distinct
- The answer fits in a 32-bit signed integer
Example 1
Input
coins = [1,2,5], amount = 5
Output
4
Explanation
The combinations are:
- 5
- 2 + 2 + 1
- 2 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1
Order does not matter, so 2 + 1 + 2 is the same as 2 + 2 + 1.
Example 2
Input
coins = [2], amount = 3
Output
0
Explanation
No number of 2-valued coins can sum to 3.
Show 1 more example
Example 3
Input
coins = [10], amount = 10
Output
1
Explanation
There is exactly one way: use one 10-valued coin.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.