Stamp Combinations for Postage
MediumBacktracking
Problem
A post office sells stamps in the distinct denominations listed in values, with an unlimited supply of each. A parcel needs postage of exactly target.
Return every distinct multiset of stamps whose values add up to target. [2, 2, 3] and [3, 2, 2] are the same combination. Return them in any order.
Example 1
- Input:
- values = [2, 3, 6, 7], target = 7
- Output:
- [[2, 2, 3], [7]]
2 + 2 + 3 = 7 and 7 = 7; no other multiset of these values sums to 7.
Example 2
- Input:
- values = [2, 3, 5], target = 8
- Output:
- [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
Constraints
- 1 ≤ values.length ≤ 30
- 1 ≤ values[i] ≤ 40
- All values are distinct.
- 1 ≤ target ≤ 40
Hint
Show the first hint
To avoid [2, 3] and [3, 2] both appearing, only add stamps in non-decreasing order of index.
Walkthrough
How to approach it
01Clarify before coding
- Can a denomination be used many times? Yes, unlimited.
- Are [2, 2, 3] and [2, 3, 2] different? No: combinations, not sequences.
- What if no combination exists? Return an empty list.
02Brute force
Generate every sequence of stamps whose sum does not exceed target, then sort and deduplicate the ones that hit target exactly.
Cost: Exponential in target with a huge factor of repeated orderings: [2, 2, 3] alone is generated 3 times, and the count grows factorially with length.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.