Coin Change II

Implement coinChangeII

Using the same unlimited-supply cashier setup as before, this time the question isn't the fewest coins but how many genuinely different ways exist to hand over the exact amount owed. Two ways of paying count as the same if they use every denomination the same number of times — reaching for a coin before or after another one doesn't create a new way, only the final tally of each denomination used does. Because order doesn't matter, coins have to be considered in a fixed sequence to avoid counting the same combination more than once: at any point, either reuse the current coin denomination again (if it still fits within what's left) or commit to moving on and never using that denomination again. Reaching a remaining amount of exactly 0 marks one valid combination; running out of denominations before that ends the path with nothing. Adding together the combinations found by reusing the current coin and by moving on to the next one counts every distinct combination exactly once.

Example 1:

Input: coins = [2,3,5], amount = 6

Output: 2

Example 2:

Input: coins = [4,6,3], amount = 10

Output: 2

Example 3:

Input: coins = [9], amount = 5

Output: 0

+ 7 hidden test cases run on Submit.

Constraints:

  • 1 ≤ coins.length ≤ 15
  • 1 ≤ coins[i] ≤ 100
  • 0 ≤ amount ≤ 1000

coins =

[2, 3, 5]

amount =

6