Show problems as
Classic problem #40MediumArrayBacktracking

Combination Sum II

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

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

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

More on the same topics