Exact Postage Stamps
A village post office sells stamps in a handful of values and has plenty of each. Every parcel needs postage that adds up to exactly the price on the scale: one coin short and it comes back, one coin over and the customer complains.
The clerk wants to see every way to make a given price from the stamp values, so she can choose the one that uses up old stock. The order the stamps are stuck on does not matter: a 2, a 3 and a 3 is the same set as a 3, a 2 and a 3.
Your task
Write stampSets(values, postage). values lists the different stamp values, and each value can be used any number of times. Return every different set of stamps whose values add up to exactly postage.
Write each set as a list of stamp values in non-decreasing order, like [2, 3, 3]. The sets themselves can be in any order. If no set works, return an empty list. For postage = 0 the only set is the empty one: return [[]].
stampSets(values: int[], postage: int) → int[][] Any order of the returned list is accepted.
Examples
values = [2, 3, 5] postage = 8
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
Four 2s make 8, so do 2 + 3 + 3 and 3 + 5. Sets like 3 + 3 + 2 are not listed again: they hold the same stamps as [2, 3, 3]. 5 + 2 leaves 1 to go, and no stamp is worth 1.
values = [4, 6] postage = 9
[]
4 and 6 are both even, so any sum of them is even and can never be 9. No set works, so the answer is an empty list.
Constraints
- 1 ≤ values.length ≤ 10
- 1 ≤ values[i] ≤ 50, all different, in any order
- 0 ≤ postage ≤ 60
- The answer contains at most 300 sets.
Start with brute force
Keep adding any stamp in any order until the total reaches or passes the postage, then sort each successful list and use a set to drop duplicates. It finds every answer, but each answer is built once for every order its stamps can be stuck on: [2, 2, 3, 3] alone is built 6 times.
With many small values the number of orders explodes far faster than the number of answers. For values 1 to 10 and postage 12 there are only 75 different sets, but 2,045 ordered ways to reach 12, and the gap widens quickly as the postage grows.
Hints
0 of 4 shown- Hint 1
Take stamps worth 2 and 3 and postage 7. Write down the answers. Is 2 + 2 + 3 a different answer from 3 + 2 + 2? How could you stop yourself from building both?
- Hint 2
Agree to stick stamps on in a fixed order: after you pick a value, you may only pick that same value or a larger one. Then each set has exactly one way to be built, so you never produce a duplicate.
- Hint 3
Sort the values. Write a recursive helper
pick(start, remaining)that tries each value from positionstartonward. After choosing the value at positioni, callpick(i, remaining − values[i]): the samei, because the same stamp may be used again. - Hint 4
When
remainingis 0, record a copy of the current set. Because the values are sorted, once a value is larger thanremaining, every later one is too, so you can stop the loop there. Push before the call and pop after it.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Duplicates come from building the same set in different orders. Fix the order instead of cleaning up afterwards: pick values in non-decreasing order, so each set has exactly one way to be built.
Trace values [2, 3, 5], postage 8:
- Pick 2, 2, 2, 2: remaining 0, record
[2, 2, 2, 2]. - Back to
[2, 2]with 4 left. Try 3: 1 left, and nothing fits, so this branch dies. 5 is bigger than 4, so stop. - Back to
[2]with 6 left. Try 3, then 3: record[2, 3, 3]. Try 5: 1 left, dead. - Back to
[]. Start with 3 (2 is no longer allowed): 3, 3 leaves 2, and nothing from 3 upward fits. 3, 5 leaves 0: record[3, 5]. - Start with 5: 3 left, and 5 is too big. Done.
Three sets, each built once. The two classic mistakes: recursing with i + 1 (each stamp used at most once, so [2, 2, 2, 2] is lost) and recursing with 0 (every order is built again, giving duplicates like [3, 2, 3]).
function stampSets(values, postage) {
const sorted = [...values].sort((a, b) => a - b);
const sets = [];
const current = [];
function pick(start, remaining) {
if (remaining === 0) {
sets.push([...current]); // exact postage reached
return;
}
for (let i = start; i < sorted.length; i++) {
if (sorted[i] > remaining) break; // later values are too big too
current.push(sorted[i]);
pick(i, remaining - sorted[i]); // i, not i + 1: reuse allowed
current.pop();
}
}
pick(0, postage);
return sets;
}def stamp_sets(values, postage):
values = sorted(values)
sets = []
current = []
def pick(start, remaining):
if remaining == 0:
sets.append(current[:]) # exact postage reached
return
for i in range(start, len(values)):
if values[i] > remaining:
break # sorted, so later values are too big too
current.append(values[i])
pick(i, remaining - values[i]) # i, not i + 1: reuse allowed
current.pop()
pick(0, postage)
return setsRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.