0268MediumArrayBacktracking

Exact Postage from a Stamp Box

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A collector keeps a shoebox of loose stamps. stamps[i] is the face value, in cents, of the i-th stamp in the box. Two stamps in the box may carry the same face value; they are still two separate stamps.

A parcel needs exactly postage cents of stamps on it. Peel stamps out of the box, using each physical stamp at most once, so that the face values add up to postage. Report every group of face values that can do this.

Write the face values inside a group in non-decreasing order. Two groups count as the same when they list the same face values the same number of times each, so report such a group once however many ways the box can supply it. The groups themselves may be returned in any order.

Examples

Example 1

Input: stamps = [3, 5, 5, 8, 12, 2], postage = 13
Output: [[2, 3, 8], [3, 5, 5], [5, 8]]

2 + 3 + 8, 3 + 5 + 5 and 5 + 8 each total 13. The pair 5 + 8 can be peeled using either of the two 5-cent stamps, and both peels give the same group of face values, so it is reported once.

Example 2

Input: stamps = [4, 4, 4], postage = 8
Output: [[4, 4]]

Two 4-cent stamps total 8. Any two of the three stamps give the group [4, 4], which is reported once.

Example 3

Input: stamps = [9, 7], postage = 5
Output: []

9, 7 and 9 + 7 are the only totals the box can make, and none of them is 5.

Constraints

1 <= stamps.length <= 100
1 <= stamps[i] <= 50
1 <= postage <= 30

The groups you return, and the values inside each group, may be in any order.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def exact_postage_sets(stamps: list[int], postage: int) -> list[list[int]]:

Java

public List<List<Integer>> exactPostageSets(int[] stamps, int postage)

The intended approach

Time O(n log n + k * 2^n) worst case, k being the size of a reported groupSpace O(postage) for the recursion path, beyond the returned groups

Sort the face values so equal ones are adjacent, then extend a partial group one stamp at a time, always drawing from a position after the last one used. Inside a single level, a face value equal to the one just tried at that level is passed over, which is what stops the same group being emitted twice. A branch is abandoned as soon as the next face value exceeds what is still owed, and since every face value is at least 1 the recursion cannot go deeper than `postage` levels.

Pythonentry point: exact_postage_sets

def exact_postage_sets(stamps, postage):
    # Sort so equal face values sit next to each other, then at each level walk
    # the sorted list and refuse a face value that was already tried at this
    # level.  Every face value is at least 1, so no reported set holds more than
    # `postage` stamps and the recursion depth stays under postage + 1.
    # Time: O(n log n) for the sort plus O(k * 2^n) worst case to enumerate the
    #       surviving branches, k being the size of a reported set.
    # Space: O(postage) for the recursion path, plus the returned sets.
    values = sorted(stamps)
    n = len(values)
    found = []
    picked = []

    def walk(start, left):
        if left == 0:
            found.append(list(picked))
            return
        i = start
        while i < n:
            v = values[i]
            if v > left:
                break
            if i > start and v == values[i - 1]:
                i += 1
                continue
            picked.append(v)
            walk(i + 1, left - v)
            picked.pop()
            i += 1

    walk(0, postage)
    return found

The obvious version

Enumerate every subset of the box with a bitmask, keep the ones whose face values total the postage, and collapse them into a set of sorted tuples to drop repeats.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_exact_postage_sets(stamps, postage):
    n = len(stamps)
    seen = set()
    for mask in range(1 << n):
        total = 0
        chosen = []
        for idx in range(n):
            if mask >> idx & 1:
                total += stamps[idx]
                chosen.append(stamps[idx])
        if total == postage:
            seen.add(tuple(sorted(chosen)))
    return [list(t) for t in sorted(seen)]

How this problem was checked

Reference solution executed against 8 test cases — 8 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in