Exact Change Bundles

medium

A vending machine stocks unlimited quantities of snacks at a few distinct price points. A customer inserts exactly budget cents and refuses any change.

Given the distinct positive integers prices and the integer budget, return every unique combination of prices that sums to exactly budget. The same price may be used any number of times. Two combinations are the same if they use the same multiset of prices, regardless of order.

Example 1

in prices = [2, 3, 6, 7], budget = 7

out [[7], [2, 2, 3]]

7 alone works, and 2+2+3 = 7. Reuse is allowed.

Example 2

in prices = [2], budget = 1

out []

Constraints

· 1 <= len(prices) <= 12
· 2 <= prices[i] <= 40 (distinct)
· 1 <= budget <= 40