Description
Given an integer array coins representing different denominations and an integer amount, return the number of combinations that make up that amount.
Examples
Input:
amount = 5, coins = [1,2,5]Output:
4Explanation:
4 ways: 5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1.
Input:
amount = 3, coins = [2]Output:
0Explanation:
Edge case returning zero.
Input:
amount = 4, coins = [1,2,3]Output:
4Explanation:
4 ways to make amount 4: 4=3+1, 4=2+2, 4=2+1+1, 4=1+1+1+1. This example demonstrates how multiple coin denominations can create various combinations.
Constraints
- •
1 ≤ coins.length ≤ 300 - •
1 ≤ coins[i] ≤ 5000 - •
0 ≤ amount ≤ 5000