Given a target amount and an array of coin denominations (unlimited supply of each), count how many distinct combinations of coins add up to the amount. Order doesn't matter — [1,2] and [2,1] are the same combination.
Example
Input amount = 5, coins = [1,2,5]
Output 4
Key Pointers
Since order doesn't matter, loop over coins in the outer loop and amounts in the inner loop — that structure counts each combination exactly once instead of counting every ordering separately.
Each coin has unlimited supply, so the inner loop walks upward through amounts, letting the same coin be reused within a single pass.
dp[0] = 1 is the base case: there's exactly one way to make amount 0 — use no coins at all.
Step-by-Step Analysis
Create a dp array of size amount + 1, all zeros, with dp[0] = 1.
For each coin denomination, walk x from that coin's value up to amount.
At each x, add dp[x - coin] into dp[x] — the number of ways to make x - coin becomes the number of new ways to make x using one more of this coin.
Finishing one coin fully before starting the next is what prevents counting the same combination in multiple orders.
Return dp[amount].
Complexity
Time: O(amount · len(coins)) — Space: O(amount)
Code
def change(amount: int, coins: list[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]
return dp[amount]
Code Explanation
How the solution above works, piece by piece.
dp[x] = number of ways to make amount x; dp[0] = 1 (use no coins).
The outer loop is over coins, so combinations are built using coin types in a fixed order. This counts combinations, not permutations.
For each amount x ≥ coin, dp[x] += dp[x - coin]: every way to make x − coin becomes a way to make x by adding this coin.
Looping x upward lets the same coin be reused (the updated dp[x - coin] may already include this coin).
O(amount × coins) time, O(amount) space.
Visual Walkthrough
Running it on amount = 5, coins = [1, 2, 5]:
Coins are added one type at a time. Looping over coins in the outer loop means each combination is counted once in a fixed order (all 1s, then 2s, then 5s), so 1 + 2 and 2 + 1 aren't counted twice. Result: 4 ways.