0175MediumArrayBacktracking

Exact Postage Mixes

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 mailroom keeps rolls of stamps. denominations lists the face values in stock, all different, and the roll for each value is effectively endless, so a value may be used as many times as you like.

A parcel needs exactly postage in stamps: no less, and no overpaying. A mix is a multiset of face values whose sum is exactly postage.

Return every distinct mix the stock allows. Two mixes are the same if one uses each face value the same number of times as the other, so [4, 4, 5] and [4, 5, 4] count as one mix. Ordering is free: the values inside a mix may be listed in any order, and the mixes themselves may come in any order. If the parcel cannot be franked exactly, return an empty list.

Examples

Example 1

Input: denominations = [4, 5, 9], postage = 13
Output: [[4, 4, 5], [4, 9]]

Two 4s and a 5 reach 13, and so does a 4 beside a 9. Nothing else sums to exactly 13.

Example 2

Input: denominations = [6], postage = 18
Output: [[6, 6, 6]]

Only one face value is stocked, and three of them land on 18, which is allowed because the roll never runs out.

Example 3

Input: denominations = [8, 11], postage = 5
Output: []

Every stocked value already exceeds 5, so the parcel cannot be franked exactly and nothing is reported.

Constraints

1 <= denominations.length <= 30
2 <= denominations[i] <= 40
All values in denominations are distinct
1 <= postage <= 40

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 postage_mixes(denominations: list[int], postage: int) -> list[list[int]]:

Java

public List<List<Integer>> postageMixes(int[] denominations, int postage)

The intended approach

Time O(k^(p/m + 1))Space O(p/m) beyond the returned mixes

Sort the face values and grow one mix by backtracking on the amount still owed. At each step only values from the current index onwards may be added, which is what stops the same multiset being built in several orders, and the current index is reused rather than advanced because a roll can be drawn from again. Sorting also lets the loop stop as soon as a value exceeds what is owed, since everything after it is larger.

Pythonentry point: postage_mixes

def postage_mixes(denominations, postage):
    # With k face values, the smallest worth m and postage p, the search tree is
    # at most p/m deep with k branches per level, so time is O(k^(p/m + 1)) and
    # the recursion plus the working mix costs O(p/m) space beyond the output.
    stock = sorted(denominations)
    mixes = []
    working = []

    def build(start, owed):
        if owed == 0:
            mixes.append(list(working))
            return
        for index in range(start, len(stock)):
            value = stock[index]
            if value > owed:
                break
            working.append(value)
            build(index, owed - value)
            working.pop()

    build(0, postage)
    return mixes

The obvious version

Build up amounts from 0 to postage. For each amount, extend every mix known for a smaller amount by one stamp and store the result as a sorted tuple in a set, which collapses reorderings. No recursion.

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_postage_mixes(denominations, postage):
    known = [set() for _ in range(postage + 1)]
    known[0].add(())
    for amount in range(1, postage + 1):
        for value in denominations:
            if value <= amount:
                for mix in known[amount - value]:
                    known[amount].add(tuple(sorted(mix + (value,))))
    return [list(mix) for mix in sorted(known[postage])]

How this problem was checked

Reference solution executed against 16 test cases — 16 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