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.