1170. Exactly k Different Digits Adding to t
Print every way to choose exactly k DIFFERENT digits from 1 to 9 whose total
is t. Each digit may be used at most once.
3 9 -> 1 2 6
1 3 5
2 3 4
## What most people try first
Enumerate all 512 subsets of the nine digits and keep the ones of the right size and total. At this size that is genuinely fine, which is worth saying out loud: 512 is nothing. The reason to do better is that the same shape appears with hundreds of values instead of nine, and the habits formed here are the ones that transfer.
## The method
Walk the digits upwards, carrying the remaining total and the digits chosen so far:
go(d, rem):
if size(cur) == k: record cur if rem == 0; return
if size(cur) + (10 - d) < k: return # not enough digits left
for v in d .. 9:
if v > rem: break # v and everything after is too big
cur.push(v); go(v + 1, rem - v); cur.pop()
Three separate prunes are at work. Stopping at size k means no branch runs
past the required length. The count test abandons a branch that cannot reach
size k even using every digit left. The break abandons the rest of the loop
once a digit no longer fits, which is sound because the digits ascend.
## Why it is correct
The search builds exactly the strictly increasing sequences of digits, since d
moves past each chosen digit, and every set of distinct digits is exactly one
such sequence. A sequence is recorded only when it has k digits and the
remaining total has reached 0, which is the condition asked for. Nothing valid
is pruned: the count test only cuts branches whose maximum reachable size is
below k, and the break only cuts digits that already exceed what is left to
make.
## 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.
## The settled boundaries
All nine digits total 45, so t above 45 always gives none. k = 9 with
t = 44 also gives none, since using all nine digits forces the total to be
exactly 45. k = 0 has exactly one answer when t = 0, the empty choice,
printed as the word empty, and none for any other t. k = 10 is
impossible, because there are only nine digits to choose from.
## Cost
At most 512 subsets exist, and the pruning visits far fewer. The recursion is at most 9 deep.
Constraints - `0 ≤ k ≤ 10` - `0 ≤ t ≤ 50`
Input
A single line containing two integers k and t.
Output
Print every choice of exactly k different digits from 1 to 9 totalling t on its own line, the digits in increasing order separated by single spaces, the lines ordered as described. Print empty for the empty choice and none if there are no choices.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.