Loading...
Loading...
Loading...
Sneha has a bookshop voucher worth exactly t rupees. The shop has n items, and some items have the same price. She wants to use the full voucher, buying each item at most once.
Print every different list of prices that adds up to exactly t. Write each list from the smallest price to the largest. Two lists with the same prices count only once, even if they use different items. Print the lists in dictionary order: compare the first prices as numbers, then the second prices, and so on. If no list works, print NONE.
NONE if there is no list.Example 1
Input
6 8 2 3 5 1 6 2
Output
1 2 2 3 1 2 5 2 6 3 5
Sorted, the prices are 1 2 2 3 5 6. The two items priced 2 give 1 2 5 twice, but it is printed once.
Example 2
Input
3 10 4 4 4
Output
NONE
Two items make 8 and three make 12, so 10 cannot be reached.
Try the problem first. Open one hint at a time.
Sort the prices. Then build each list from left to right, and only pick items after the last one you picked.
Pass the amount still left to spend. When it reaches 0, print the list. When a price is bigger than the amount left, stop the loop: every later price is bigger too.
Equal prices cause repeated lists. At one level of the search, skip an item when it has the same price as the item just before it in that same loop.
Use a flag to remember whether you printed anything, and print NONE at the end if you did not.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor