Start learning free

LESSON 532 OF 675 · DYNAMIC PROGRAMMING

Coin Change II

Practice O(n · amount)

You get an integer amount and an array coins of different coin values.

Return how many combinations of coins add up to exactly amount.

You can use each coin value as many times as you like. If no combination makes amount, return 0.

The order of the coins doesn't matter. So 3 + 5 and 5 + 3 are one combination.

 

Example 1:

Input: amount = 8, coins = [2, 3, 5]
Output: 3
Explanation: The three combinations are:
8 = 2 + 2 + 2 + 2
8 = 2 + 3 + 3
8 = 3 + 5

Example 2:

Input: amount = 5, coins = [3, 4]
Output: 0
Explanation: One coin makes 3 or 4.
Two or more coins make at least 6.
So no combination makes 5.

Example 3:

Input: amount = 0, coins = [7]
Output: 1
Explanation: Taking no coins at all makes 0.
That counts as one combination.

 

Constraints:

  • coins holds 1 to 300 different values.
  • Each value is from 1 to 5,000.
  • amount is from 0 to 5,000.
  • The answer fits in a 32-bit signed integer.
  • The count for every smaller amount fits too.

Note:

Your algorithm should run in O(n · amount) time and O(amount) space, where n is the number of coins.



Listing every combination is far too slow: a few dozen coins can make more than a billion combinations of 5000. Count them instead: let ways[a] be the number of combinations that make the sum a, for every a from 0 to amount. Start with ways[0] = 1, the combination of no coins, and every other entry at 0. The answer is ways[amount].

Add the coins one at a time, in an outer loop. For each coin, go over the sums a from coin up to amount and add ways[a - coin] to ways[a]: every combination for a - coin, plus one more of this coin, is a combination for a. Going up lets ways[a - coin] already contain this coin, so it can be used many times.
Why the coins must be the outer loop: when a coin is added, the counts so far only use the coins before it. So every combination is built in one fixed order, first all its coins of the first value, then all of the second, and so on, and it is counted exactly once: 1 + 3 is counted, 3 + 1 never is. With the sums outside and the coins inside, any coin could be the last one added to any sum, so 1 + 3 and 3 + 1 would both be counted: that counts orders, not combinations.

Each of the n coins goes over at most amount + 1 sums, with a constant amount of work for each: O(n · amount) time. ways holds amount + 1 counts: O(amount) space.
STEP 1 OF 6
    Ctrl + Enter to check