Coin Change Ways

Count the distinct ways to make a target amount using given coin denominations.

dynamic programming coins counting combinations

You have an unlimited supply of coins with given denominations. Write a function `coin_change_ways(coins, amount)` that returns the number of distinct combinations of coins (order does not matter) that sum to exactly `amount`. If it is impossible, return 0.

- `coins` is a list of positive integers representing distinct denominations.
- `amount` is a non-negative integer.
- You may use each denomination any number of times.
- Two combinations are considered the same if they contain the same multiset of coins (e.g., [1,2] and [2,1] are the same).
- The result is guaranteed to fit within a 64-bit signed integer.

Constraints

- 1 <= len(coins) <= 10
- 1 <= coins[i] <= 1000
- 0 <= amount <= 1000
- All coin denominations are distinct.
- Time and memory should be O(len(coins) * amount) or better.

Example

>>> coin_change_ways([1, 2, 5], 5)
4
>>> coin_change_ways([2], 3)
0
>>> coin_change_ways([3, 5, 7], 0)
1

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of a table where dp[x] is the number of ways to make amount x using the coins processed so far.

For each coin, update the dp array from coin up to amount, adding dp[x - coin] to dp[x].

Start with dp[0] = 1, because there is one way to make zero: use no coins.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.