How do you approach Coin Change II?

Iterate coins in the OUTER loop to count unordered combinations (not permutations).

What are common mistakes on Coin Change II?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Coin Change II

MediumAlgorithms

Description

You are given an integer array coins of distinct denominations and an integer amount. Return the number of combinations that make up amount. You may use each coin an unlimited number of times. If no combination works, return 0.

Combinations are unordered: {1,2} and {2,1} count once.

Example 1

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

Output: 4

Explanation: 5=5, 2+2+1, 2+1+1+1, 1+1+1+1+1.

Example 2

Input: amount = 3, coins = [2]

Output: 0

Explanation: Cannot form 3 with only 2s.

Constraints

- 1 <= coins.length <= 300 - 1 <= coins[i] <= 5000 - 0 <= amount <= 5000

Coin Change II: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (5 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 2-step hint ladder

Iterate coins in the OUTER loop to count unordered combinations (not permutations).
dp[a] += dp[a - coin] for each amount a >= coin.

The optimal approach

Show the approach: The approach

Unbounded knapsack counting. `dp[a]` is the number of ways to make amount `a`. Process each coin once (outer loop) and update amounts in increasing order so each combination is counted once regardless of order.

Time: O(coins·amount). Space: O(amount).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.