A shop sells gift items at n distinct prices, with unlimited stock of each. List every way to fill a basket whose prices add up exactly to T. A basket is a multiset, so write each one with its prices in non-decreasing order, and list the baskets in lexicographic order (compare the first price, then the second, and so on; a basket that is a prefix of another comes first).
Print the number of baskets, then one basket per line.
Constraints
- 1 ≤ n ≤ 20
- 1 ≤ T ≤ 40
- 1 ≤ price ≤ 40
- the answer has at most 2000 baskets
Input and output
- Input
- Line 1: n and T. Line 2: n distinct prices.
- Output
- Line 1: the count c. Next c lines: one basket, prices separated by spaces.
Examples
Input 1
3 8
2 3 5Output
3
2 2 2 2
2 3 3
3 5Three baskets: 2+2+2+2, 2+3+3 and 3+5.
Input 2
2 1
2 3Output
0Nothing adds up to 1, so the count is 0 and no lines follow.
Show hints
- Sort the prices first.
- Recurse with a start index so each basket is built in non-decreasing order and generated exactly once.
Show the explanation
Backtracking: sort the prices, then build a basket left to right. At each step, try prices from the current index onward (staying at the same index allows reuse), subtract it from the remaining target, and recurse; undo the choice afterwards. Stop a branch when a price exceeds what remains — since prices are sorted, every later price will too. Because choices never go back to a smaller index, each multiset is produced exactly once, and in lexicographic order.
Original UniCircle question. Last reviewed 22 Oct 2026.