Coin Change II

Given distinct positive denominations coins and a positive amount, count the unordered combinations whose values sum exactly to amount. You may use each…

Given distinct positive denominations coins and a positive amount, count the unordered combinations whose values sum exactly to amount. You may use each denomination any number of times. Different orders of the same multiset are one combination. Return the count modulo 1,000,000,007; return 0 when no combination exists.

- 1 <= number of denominations <= 1000. - Denominations are distinct integers from 1 through 1000, in any order. - 1 <= amount <= 1000. - The visualizer accepts at most 6 denominations and amount at most 10; larger valid inputs are coding-only.

Example 1: input coins = [1,2,3], amount = 4; output 4. The multisets are four 1s, two 1s and one 2, two 2s, and one 1 with one 3. Reordering these coins adds no combination.

Example 2: input coins = [2,5], amount = 6; output 1. Three copies of denomination 2 make 6. A denomination can be reused.

Example 3: input coins = [4,6], amount = 5; output 0. Neither denomination nor any nonnegative combination totals 5.

Category: Arrays. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.