Count how many distinct combinations of coins sum to a target amount, where each coin type can be used any number of times.
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.
coins: an array of positive integers representing coin denominationsamount: a non-negative integer target sumamount1 <= coins.length1 <= coins[i]amount >= 0Example 1
Input
coins = [1,2,5], amount = 5
Output
4
Explanation
The combinations are:
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.
Example 3
Input
coins = [10], amount = 10
Output
1
Explanation
There is exactly one way: use one 10-valued coin.
Premium problem context
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.