Skip to content
BASA DSA

Coin Change II

Medium2-D Dynamic Programming

Count distinct multisets of coins summing to amount, with unlimited copies of each denomination. Different orders of the same coins count once; amount zero has one empty combination.

Example 1

Input
amount = 6
coins = [1,3,4]
Output
4

Explanation

The multisets are six 1s, 3 plus three 1s, two 3s, and 4 plus two 1s.

Example 2

Input
amount = 7
coins = [2,4]
Output
0

Explanation

Even-valued coins cannot total odd amount 7.

Example 3

Input
amount = 0
coins = [3]
Output
1

Explanation

Zero has one combination: choose no coins.

Constraints

  • 0 <= amount <= 5000
  • 1 <= number of distinct positive coins <= 300
  • The answer fits a signed 32-bit integer

Function contractchangeArguments: json, json
Loading draft…
SolutionRuns on your device