Skip to main content

518. Coin Change II

medium

Count the number of distinct coin combinations that sum to amount. The order-doesn't-matter cousin of Coin Change — process coins as the outer loop to avoid permutation overcounting.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0. You may assume that you have an infinite number of each kind of coin. The answer is guaranteed to fit into a signed 32-bit integer.

Constraints

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • All the values of coins are unique.
  • 0 <= amount <= 5000

Examples

Example 1

Input
amount = 5, coins = [1,2,5]
Output
4

Explanation: There are four ways to make up the amount: 5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1.

Example 2

Input
amount = 3, coins = [2]
Output
0

Explanation: The amount of 3 cannot be made up just with coins of 2.

Example 3

Input
amount = 10, coins = [10]
Output
1

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

If you iterate amounts on the outside you count permutations (1+2 and 2+1 separately). Wrong.

Hint 2

Iterate coins on the outside. For each coin, sweep amounts and let dp[a] += dp[a - coin].

Hint 3

Base case dp[0] = 1 (one way to make 0 — pick nothing).

Solution approach

Reveal approach

Use a 1D dp where dp[a] is the number of combinations summing to a. Initialize dp[0] = 1 and dp[a] = 0 elsewhere. Crucially iterate coins as the OUTER loop and amounts as the INNER loop: for each coin c, for a from c to amount, dp[a] += dp[a - c]. This ordering ensures each combination is counted exactly once because by the time you finish processing coin c you have committed to whether the combination uses any c's before moving to the next denomination. The reverse loop order would count (1,2) and (2,1) as distinct (permutations). Return dp[amount]. O(N * amount) time.

Complexity

Time
O(N * amount)
Space
O(amount)

Related patterns

  • dynamic-programming
  • unbounded-knapsack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Coin Change II and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →