482. Combinations to Make an Amount

Coins of k distinct denominations are available in unlimited supply. Count the distinct MULTISETS of coins that sum to exactly amount. Two selections using the same coins in a different order are the SAME multiset and count once.

Print the count modulo 1000000007.

coins 1 2 5, amount = 11 -> 11 coins 2, amount = 3 -> 0

Problem #410 counts ORDERED sequences on the same input, and on coins 1 2 5 with amount = 11 it answers 218. Same coins, same amount, two answers that differ by a factor of twenty.

The two problems differ by nothing except the ORDER OF TWO LOOPS, and that is the single most important thing to know about knapsack counting.

## The two loop orders

``` dp[0] = 1

COMBINATIONS PERMUTATIONS for each coin c: for v in 1..amount: for v in c..amount: for each coin c <= v: dp[v] += dp[v - c] dp[v] += dp[v - c] ```

Both are three lines. Both fill the same array. One counts multisets and the other counts sequences.

## Why the outer loop over coins gives multisets

Fix the order in which the coins are processed. When coin c is being processed, every dp[v] already counts selections using only the coins BEFORE c, and the update adds selections whose largest-indexed coin is c.

So each multiset is counted exactly once, at the moment its highest-indexed coin is processed. The coin order imposes a canonical form on the multiset, and a canonical form is what makes a count a count of multisets.

Reverse the loops and dp[v] is built by asking "what was the LAST coin added", which distinguishes 1 then 2 from 2 then 1. That is a count of sequences.

## Unlimited supply

The inner loop runs FORWARD, from c up to amount. That is deliberate: dp[v - c] has already been updated for coin c in this same pass, so coin c can be used again.

Running it backward gives 0/1 counting, where each coin is used at most once, which is problem 483 with different data. Forward for unlimited, backward for at-most-once, and the direction of one loop is the whole difference.

## Boundaries

amount = 0 answers 1, the empty multiset. That is the dp[0] = 1 base case and it is not a special case to write: every other entry is built from it.

coins 2, amount = 3 answers 0. An amount with no representation returns 0, not -1, because 0 is the true count.

The count grows fast, which is why the modulus is in the statement. coins 1 5 10 25 with amount = 30 answers 18, well under the modulus, but at the constraint bounds it would not be.

Constraints - `1 ≤ k ≤ 100` - `0 ≤ amount ≤ 5000` - `1 ≤ denomination ≤ 5000` - the denominations are distinct