Coin Change II is a classic dynamic programming problem that focuses on counting combinations, not finding the minimum coins. You are given an array of coin denominations and a target amount. Your task is to determine how many different ways you can make up that amount using the given coins.
Each coin can be used an unlimited number of times. The order of coins does not matter. That detail is critical.
For example, if the amount is 5 and the coins are [1, 2, 5], then 1 + 2 + 2 and 2 + 1 + 2 are considered the same combination, not different ones.
This problem often appears in interviews because it tests whether you understand the difference between combinations and permutations, and whether you can design a dynamic programming solution that avoids double-counting.
Why many first attempts go wrong
A common mistake is to treat this like a permutation problem.
If you build solutions by trying all coin choices at every step, you’ll end up counting the same combination multiple times in different orders. That leads to incorrect results even if the logic seems reasonable.
Another mistake is trying to use recursion without memoization. That approach quickly becomes slow because the same subproblems are recomputed again and again.
The challenge is not just finding a working solution. It is structuring the solution so that each valid combination is counted exactly once.
The core idea behind the solution
The key insight is to control the order in which coins are introduced.
Instead of asking, “What coins can I use next?”, you ask:
“How many ways can I make this amount using only the first k coins?”
That shift in perspective prevents duplicates.
Want to explore more coding problem solutions? Check out the Maximum Sum Circular Subarray and Partition List coding problem solutions.
How the dynamic programming approach works
You create a one-dimensional table where each position represents an amount from 0 up to the target.
The value at each position represents the number of ways to make that amount.
You start with the base case: there is exactly one way to make amount 0, which is using no coins at all.
Then you process coins one by one.
For each coin, you walk through the amounts from the coin’s value up to the target amount.
At each amount, you update the number of ways by adding the number of ways to make the remaining amount after using that coin.
Because you process coins in a fixed order and never go backward to earlier coins, each combination is built in only one way. This is what avoids counting permutations.
Why the order of loops matters
This is the most important conceptual point.
Coins go in the outer loop. Amounts go in the inner loop.
If you reverse that order, you accidentally count different orders of the same coins as different solutions.
Interviewers often ask about this explicitly because it shows whether you truly understand the problem or just memorized a pattern.
Intuition behind correctness
Every combination can be described as:
- zero or more uses of coin 1
- zero or more uses of coin 2
- and so on
By processing coins sequentially, you ensure that when you consider a coin, all combinations formed so far already respect the ordering constraint.
Each update extends existing combinations in a controlled way, without creating duplicates.
Performance in simple terms
The solution runs in time proportional to the number of coins multiplied by the target amount.
Space usage is linear in the target amount.
This is efficient and well within typical interview limits.
Top comments (0)