Coin Change II

Medium· unbounded knapsack· counting

Problem

Given coin denominations with unlimited supply and a target amount, count the number of distinct combinations of coins that sum to the amount. Order does not matter, so 1+2 and 2+1 are the same combination.

Examples

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

Output: 4

5, 2+2+1, 2+1+1+1, 1+1+1+1+1.

Input: amount = 3, coins = [2]

Output: 0

Constraints

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

Hints & approach

Hint 1

Counting orderings and counting combinations are different problems.

Hint 2

Process one coin type at a time so each combination is built in a fixed coin order.

Hint 3

For each coin c, for a from c upward: ways[a] += ways[a - c].

Approachtry the hints first

Let ways[a] be the number of combinations summing to a using the coins seen so far, with ways[0] = 1. Loop over coins in the outer loop and amounts in the inner loop, ascending, adding ways[a-c] into ways[a]. Putting coins outside ensures every combination is counted once in a canonical order, and iterating amounts upward allows unlimited reuse of the current coin.

Time O(n·amount) · Space O(amount)

← PreviousCoin Change Next →Partition Equal Subset Sum