Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 518 Coin Change II - Problem Statement

LeetCode 518

Given coins of different denominations and a total amount, return the number of combinations to make that amount. You can use each coin unlimited times. For example, with coins [1,2,5][1, 2, 5] and amount 55, there are 44 ways: [5],[2,2,1],[2,1,1,1],[1,1,1,1,1][5], [2,2,1], [2,1,1,1], [1,1,1,1,1]. This is unbounded knapsack with counting.

But there's a trap. Notice the problem says "combinations", not "permutations". Using [1,2][1,2] and [2,1][2,1] counts as one way, not two. If you're not careful, your DP will count permutations instead. The fix involves loop order, which trips up a lot of people.