1154. Selections That Stay Under a Limit
Given n distinct positive integers and a limit t, print every selection
whose total is at most t.
3 4
1 2 3 -> empty
1
1 2
1 3
2
3
1 2 3 totals 6 and is left out. 2 3 totals 5 and is left out too.
## What most people try first
Enumerate all 2^n selections and keep the ones whose total fits. It is
correct, and at n = 20 it is a million selections regardless of the limit: a
limit of 1 against twenty values of a thousand each produces one line after a
million steps.
## The method, and why one word of it matters
Sort the values, carry the REMAINING allowance down the recursion, and inside the loop stop at the first value that no longer fits:
go(i, rem):
record cur
for j in i .. n-1:
if a[j] > rem: break # not continue
cur.push(a[j]); go(j + 1, rem - a[j]); cur.pop()
break, not continue. The values are sorted and positive, so if a[j] is
already too big then every value after it is bigger still and cannot fit
either. continue would keep testing all of them and get the same answer more
slowly; break abandons the rest of the loop, and that is what turns the cost
from "always 2^n" into "proportional to the answer".
## Why it is correct
The record happens on entry, so each node of the search records the selection
it represents, and the loop extends it with any later index. Every selection
with increasing indices is therefore reached along exactly one path. A
selection is recorded only when its total is at most t, because rem starts
at t and each push subtracts the value pushed, so rem at any node is
exactly t minus the total of cur, and the branch is only entered when the
value fits inside what is left.
Nothing legal is pruned away: the values are positive and sorted, so once
a[j] > rem holds, every a[j'] with j' > j satisfies a[j'] >= a[j] > rem
and every selection through those branches would exceed the limit as well.
## The output convention, shared by every problem in this block
Values inside one selection are separated by single spaces and printed in
increasing order. Selections are printed one per line. Two selections are
ordered by comparing them position by position NUMERICALLY, and when one is a
prefix of the other the shorter one comes first, so the empty selection is
always first. The empty selection prints as the word empty. If there are no
selections at all, print none.
The empty selection totals 0, and t is at least 0, so there is always at
least one answer and none is never printed.
## Overflow
Values reach 100000 and n reaches 18, so a total reaches 1.8 * 10^6, and
t reaches 10^9. All of those sit inside a signed 32 bit integer, whose top
is 2147483647, so nothing here overflows. Keeping rem as a running
subtraction rather than recomputing sum(cur) is about speed, not about width.
## Cost
Proportional to the number of answers times O(n) to print each, plus one
wasted test per pruned loop.
Constraints - `1 ≤ n ≤ 18` - `0 ≤ t ≤ 10^9` - `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 selection whose total is at most t on its own line, values in increasing order separated by single spaces, the lines ordered as described. The empty selection prints as empty.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.