Show problems as
Classic problem #39MediumArrayBacktracking

Combination Sum

Real-world version: Exact Postage Mixes
Tracked in this browser only
Read Combination Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstBacktracking · Recursion, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def postage_mixes(denominations: list[int], postage: int) -> list[list[int]]:
Java
public List<List<Integer>> postageMixes(int[] denominations, int postage)

More on the same topics