1173. Combinations Within a Length Budget
Given n distinct positive values, reusable without limit, a target t and a
budget m, print every combination totalling t that uses at most m values.
3 7 3
2 3 6 -> 2 2 3
With m = 3 the only combination within budget is 2 2 3. With m = 2 there
is none, because no two of 2 3 6 total 7.
## What most people try first
Run problem 1168 unchanged and discard the combinations that are too long. That
is correct and it keeps descending down branches that have already run out of
budget: with the value 1 available and t = 30, the search walks all thirty
levels before noticing that m was 4.
The first fix is to stop when the budget runs out, which is one line and removes most of the waste. The second fix is the interesting one.
## Two prunes, one obvious and one not
go(i, rem):
if rem == 0: record cur; return
slots = m - size(cur)
if slots == 0: return # out of budget
if slots * largest value < rem: return # cannot possibly finish
for j in i .. n-1:
if a[j] > rem: break
cur.push(a[j]); go(j, rem - a[j]); cur.pop()
The first test stops a branch that has spent its budget. The second looks
FORWARD: even filling every remaining slot with the largest available value
gives at most slots * largest, so if that is below the remainder the branch is
already dead, however many slots are left. It cuts the branch many levels before
the budget would.
## Why it is correct
The search builds each non-decreasing sequence exactly once, as in problem 1168,
and records it when the remainder reaches 0, which can only happen with at most
m values because the budget test refuses a push once slots is 0.
Neither prune removes an answer. The budget test is exact. The forward bound is
sound because any completion of the current prefix adds at most slots values,
each at most the largest value in the set, so its total is at most
slots * largest; if that is below rem no completion exists. It is an
optimistic bound, meaning it may leave some dead branches alive, but it never
cuts a live one, and that asymmetry is what makes a bound usable.
## The output convention, shared by every problem in this block
Each combination is printed on its own line with single spaces between its
values. Two combinations are compared position by position NUMERICALLY, and
when one is a prefix of the other the shorter comes first. If no combination
reaches the target, print none.
A budget of 0 admits only the empty combination, which totals 0, and t is at
least 1, so m = 0 always prints none.
## Overflow
slots * largest is at most 8 * 100, which is 800, so nothing here comes
close to the 2147483647 a signed 32 bit integer holds. The habit is still
worth naming: a bound computed as a product is the place in a search where an
overflow turns a prune into nonsense, because a wrapped product compares as
smaller than the remainder and the branch is cut even though it contains
answers. With a budget in the thousands and values near 10^9 that
product reaches 10^12, which a 32 bit type cannot hold.
## Cost
Proportional to the number of answers times O(m) to print, plus the pruned
tests. The recursion is at most m deep, which is 8 here.
Constraints - `1 ≤ n ≤ 8` - `1 ≤ t ≤ 30` - `0 ≤ m ≤ 8` - `1 ≤ a[i] ≤ 100` - All values are distinct.
Input
The first line contains three integers n, t and m.
The second line contains n space-separated distinct positive integers.
Output
Print every combination totalling t that uses at most m values on its own line, its values in non-decreasing order separated by single spaces, the lines ordered as described. Print none if there is no such combination.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.