Stamp Sets for Exact Postage

A post office sells stamps in the denominations listed in values (all distinct positive integers), and you may buy as many of each as you like. Return every multiset of stamps whose total is exactly postage. Write each multiset as a non-decreasing list; the lists may be returned in any order, and no multiset may appear twice.

Examples

Input:  values = [2, 3, 7], postage = 7
Output: [[2, 2, 3], [7]]

Input:  values = [3, 5], postage = 11
Output: [[3, 3, 5]]

Input:  values = [4, 6], postage = 5
Output: []

Constraints

• 1 <= len(values) <= 8, 1 <= values[i] <= 30, distinct
• 0 <= postage <= 30
• Fewer than 1000 multisets in every test.

Goals

• Allow a candidate to be reused by recursing with the same start index
• Prune branches whose partial sum already exceeds the target