MediumArrayDynamic Programming

Coin Change II

1 approach, code in every language

You are given an integer amount representing a total amount of money, and an array of distinct coin denominations. You have an unlimited number of coins of each denomination.

Count how many distinct combinations of coins add up exactly to amount. Two combinations are considered the same if they use the same multiset of coins, so ordering does not matter (using coins 1 then 2 is the same combination as 2 then 1).

Return that count. If no combination can make up the amount, return 0. There is always exactly one way to make amount 0: use no coins.

Example 1

Input: amount = 5, coins = [1,2,5]

Output: 4

The combinations are 5, 2+2+1, 2+1+1+1, and 1+1+1+1+1, giving four distinct ways.

Example 2

Input: amount = 3, coins = [2]

Output: 0

With only coins of value 2 you can never reach an odd total like 3, so there are zero combinations.

Constraints

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All values in coins are distinct
0 <= amount <= 5 * 10^3

Unbounded Knapsack with Coins in the Outer Loop

Accumulate combination counts with dp[a] += dp[a - coin], placing coins in the outer loop and amount in the inner ascending loop so each combination is counted exactly once.

Loading animation…

Intuition

Because coins are unlimited, this is an unbounded knapsack where we count combinations rather than minimize coins. The subtle part is avoiding double counting of the same multiset in different orders. Putting the coin loop on the outside means we fully incorporate one denomination before moving to the next, so combinations are built in a fixed coin order and never permuted. Iterating the amount ascending lets a single coin be reused multiple times, which is exactly the unbounded behavior we want. The recurrence dp[a] += dp[a - coin] adds all ways to form a - coin and then extend them with the current coin.

Algorithm walkthrough

1Create a count array dp of size amount + 1 filled with zeros, then set dp[0] = 1 because there is exactly one way to make zero: pick nothing.
2Loop over each coin in the outer loop so its contribution is finalized before the next coin is considered.
3For the current coin, loop a from coin up to amount in ascending order.
4Update dp[a] += dp[a - coin]; the ascending order permits reusing the same coin any number of times.
5Return dp[amount], the total number of order-independent combinations that sum to amount.

Implementation

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for a in range(coin, amount + 1):
                dp[a] += dp[a - coin]
        return dp[amount]

Time

O(coins.length * amount) since each coin sweeps the amount range once.

Space

O(amount) for the single one-dimensional count array.

Reversing the loop order (amount outer, coins inner) would instead count ordered sequences, which is the Combination Sum IV problem, not this one.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Ribbon Spool Assemblies is our own problem on the technique behind Coin Change II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free