Basic example
Input
amount = 5, coins = [1, 2, 5]
Output
4
Combinations: {1+1+1+1+1}, {1+1+1+2}, {1+2+2}, {5}
Full lesson preview
Count ways to make change
Compute the number of distinct combinations to form a target amount using unlimited coins.
Python practice14 minDynamic ProgrammingIntermediateLast updated March 29, 2026
Problem statement
Given an integer amount and a list of distinct positive coin denominations, return the number of distinct ways to make the amount using any number of coins of each denomination. Two ways are considered different if the counts of at least one coin denomination differ. The order of coins does not matter (i.e., combinations, not permutations).
Task
Implement a dynamic programming solution that counts combinations (order doesn't matter) to make a target amount using given coin denominations.
Examples
Input format
Function count_ways(amount: int, coins: List[int])
Output format
Return an integer representing the number of combinations to make the amount.
Constraints
0 <= amount <= 1000. 0 <= len(coins) <= 50. Coin denominations are positive integers. Result fits in a 64-bit signed integer.
Samples
Sample 1
Input
count_ways(0, [1,2])
Output
1
There is exactly one way to make amount 0: choose no coins.