498. Multisets of Exactly k Coins

Coins of m distinct denominations are available in unlimited supply. Count the MULTISETS of exactly k coins summing to exactly amount. Order does not matter.

Print the count modulo 1000000007.

coins 1 2 3, k = 3, amount = 6 -> 2 {1,2,3} and {2,2,2} coins 1 2 3, k = 4, amount = 8 -> 3 {1,1,3,3} {1,2,2,3} {2,2,2,2} coins 1, k = 3, amount = 4 -> 0 three 1s cannot make 4

Problem 482 counts multisets with no size restriction. Pinning the size adds an axis, and the interest is in what each of the three loops now has to do.

## The table

dp[j][v] = multisets of exactly j coins summing to exactly v dp[0][0] = 1

for each denomination c: outer, for MULTISETS for j in 1..k: ascending, for UNLIMITED supply for v in c..amount: ascending dp[j][v] += dp[j-1][v-c]

## Three loops, three separate reasons

The DENOMINATION loop is outermost, and that is what makes the count a count of multisets rather than sequences, exactly as in problem 482: each multiset is counted once, when its highest-indexed denomination is introduced.

The COUNT loop ascends. Within one denomination, dp[j][v] reads dp[j-1][v-c], which must already include uses of the SAME denomination if that coin is to be used more than once. Ascending j provides that. Descending j would give at-most-one-of-each, which is a different problem.

The VALUE loop ascends too, but here it does not matter: dp[j][v] only ever reads row j-1, never row j, so nothing in this row is read after being written. Being able to say which loop directions are load-bearing and which are free is the useful part.

## Why the count axis replaces the usual unbounded trick

In problem 482 unlimited supply came from reading dp[v - c] in the SAME row, already updated. Here the read is always from j-1, so that mechanism is gone, and repetition of a coin is expressed by descending one step in j instead.

Two different encodings of the same freedom, and the size axis is what makes the second one available.

## Boundaries

coins 1, k = 3, amount = 3 answers 1 and k = 3, amount = 4 answers 0. With a single denomination the size and the total determine each other, so almost every pair is impossible, which is the cleanest check that both axes are being respected.

coins 5, k = 2, amount = 10 answers 1.

amount and k are independent, so an answer of 0 is common and correct. It is never -1.

## Cost

Time O(m * k * amount). Space O(k * amount).

Constraints - `1 ≤ m ≤ 50` - `1 ≤ k ≤ 50` - `0 ≤ amount ≤ 2000` - `1 ≤ denomination ≤ 2000` - the denominations are distinct