mediumDynamic Programming 1DIndian domain~25 min
Count Ways to Make an Amount from Note Denominations
A cash-handling service counts how many distinct combinations of rupee note denominations add up to a requested payout. Notes of each denomination are unlimited; order does not matter.
Problem
Given an integer amount and an array coins of distinct denomination values (unlimited supply of each), return the number of distinct combinations that sum to amount. Combinations differing only in order count once.
Input
An integer amount and an array coins of distinct positive denominations.
Output
An integer: the number of combinations summing to amount.
Constraints
- 1 <= coins.length <= 300
- 1 <= coins[i] <= 5000, all distinct
- 0 <= amount <= 5000
Examples
Example 1
Input
amount = 5, coins = [1,2,5]
Output
4
5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1.
Example 2
Input
amount = 3, coins = [2]
Output
0
No combination of 2s makes 3.