Loading
Loading
A vending machine dispenses voucher codes in a few fixed denominations, and any denomination may be dispensed as many times as needed. Support wants a list of every distinct way to make an exact total.
Given distinct positive values and a total, return every multiset of values summing to exactly total. Two bundles that differ only in order are the same bundle. Write each bundle smallest value first, comma-separated inside square brackets with no spaces, and list the bundles in lexicographic order as number sequences.
values = [3, 2, 5], total = 8[2,2,2,2]keep taking 2 until the total is met[2,2,2] + 3?9 overshoots — and 5 would too, so stop trying[2,3,3]after a 3, only 3 or larger may follow[3,5]starting from 3 never revisits 2["[2,2,2,2]", "[2,3,3]", "[3,5]"]Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(answers · total) time · O(total) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
2+2+2+2, 2+3+3 and 3+5. Each bundle is written smallest value first.
Example 2
No number of 4s makes 6, so the list is empty.