All problems

Exact Postage

Medium · backtracking

A small post office sells stamps of several values. The list values holds the worth of each kind of stamp (all different), and stock[i] is how many stamps of kind i the office has left. A parcel needs postage worth exactly target.

A plan says how many stamps of each kind to stick on: it is a list of the same length as values, where plan[i] is the number of stamps of kind i, between 0 and stock[i]. A plan is valid when the stamps add up to exactly target.

Return every valid plan, each exactly once. The plans may be returned in any order. If no plan works, return an empty list.

Examples

Example 1

Input: values = [2, 3, 5], stock = [2, 2, 1], target = 7

Output: [[1, 0, 1], [2, 1, 0]]

Two 2s and one 3 make 7, and so do one 2 and one 5. Using the 3 twice leaves 1, which no stamp can make.

Example 2

Input: values = [4, 6], stock = [3, 3], target = 5

Output: []

Every stamp is worth an even number, so an odd total is impossible.

Example 3

Input: values = [1, 2], stock = [2, 1], target = 3

Output: [[1, 1]]

One 1 and one 2. Three 1s would make 3 as well, but only two are in stock.

Constraints