1148. Combinations That Add Up
Given n distinct positive integers and a target t, print every subset
that sums to exactly t, one per line, in lexicographic order. Each value may
be used at most once. If no subset reaches the target, print none.
Problem #229 asks only whether such a subset exists and #231 counts the ways. Printing the subsets themselves is the enumeration.
Sorting first makes a real pruning rule available: walking the values in increasing order, once the remaining target goes below the current value, every value after it is larger and no branch from here can succeed. Stopping there rather than exploring is the difference between finishing and not.
Constraints - `1 ≤ n ≤ 18` - `1 ≤ t ≤ 100000` - `1 ≤ a[i] ≤ 100000` - All values are distinct.
Input
The first line contains two integers n and t.
The second line contains n space-separated distinct positive integers.
Output
Print every subset summing to t on its own line, values in increasing order separated by single spaces, the lines in lexicographic order. Print none if there are no such subsets.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.