Count ways to make exact postage from limited stamp counts
A self-service post office kiosk prints postage from a drawer of pre-printed stamps. The drawer holds a limited number of each stamp value. Before it asks the customer to choose, the kiosk shows how many different ways there are to pay the exact postage with what is left in the drawer.
Implement countStampSets(stamps, postage). It returns the number of different selections of stamps whose values add up to exactly postage.
countStampSets(stamps, postage) // => number
stamps is an array of { value, count }: count stamps of that value are in the drawer. value is a positive integer, and count is an integer from 0 to 1000.value can appear in several entries. Stamps of the same value are identical, so the entries add up: [{ value: 5, count: 2 }, { value: 5, count: 1 }] is three 5-stamps.postage is an integer from 0 to 2000.stamps.0 and the number available. Order does not matter: 5 + 2 and 2 + 5 are the same selection.0 has exactly one selection: use no stamps.0 if the postage cannot be paid exactly.Number.MAX_SAFE_INTEGER.countStampSets([{ value: 1, count: 2 }, { value: 2, count: 1 }], 2);
// => 2 (2) or (1 + 1)
countStampSets([{ value: 1, count: 10 }, { value: 2, count: 10 }, { value: 5, count: 10 }], 5);
// => 4 (5), (2 + 2 + 1), (2 + 1 + 1 + 1), (1 + 1 + 1 + 1 + 1)
countStampSets([{ value: 1, count: 1 }, { value: 2, count: 2 }, { value: 5, count: 1 }], 5);
// => 2 (5) or (2 + 2 + 1); the others need more 1-stamps than the drawer has
countStampSets([{ value: 5, count: 2 }, { value: 5, count: 1 }], 10); // => 1
countStampSets([], 0); // => 1
countStampSets([{ value: 4, count: 3 }], 6); // => 0
Tests use postage up to 2000 with up to 1000 stamps of a value. Trying every combination, or looping over every possible count of each value for every amount, is too slow.