1193. Every Split Into At Most k Groups

There are n items, numbered 1 to n. Print every way to put them into AT MOST k groups, where every group used holds at least one item.

Problem #1192 asks for exactly k groups. This asks for any number from 1 up to k, which is a smaller change to the code than it looks and a useful one to make deliberately rather than by accident.

3 items, at most 2 groups -> 1 1 1 all together 1 1 2 item 3 alone 1 2 1 item 2 alone 1 2 2 item 1 alone

With k = 3 a fifth line appears, 1 2 3, every item alone. The total when k is at least n is the Bell number of n: 1, 2, 5, 15, 52, 203.

## What most people try first

Run #1192 once for each group count from 1 to k and concatenate the outputs. That gives the right SET of answers in the wrong ORDER: it prints every one-group split, then every two-group split, and the required order is lexicographic across all of them together, which interleaves them. 1 1 2 comes before 1 2 1, and both come after 1 1 1, regardless of how many groups each uses.

The fix is not to sort afterwards. It is to drop the group count from the accept test and leave the search alone, which produces the right order directly.

## The output convention, which is most of the problem

A split has no natural order. The split that puts items 1 and 3 together and item 2 alone is the SAME split however you name the groups, so {{1,3},{2}} and {{2},{1,3}} are one answer and not two. A search that picks a group for each item finds that one answer k! different ways unless something stops it.

So the printed form is fixed, and it is fixed in a way that admits exactly one spelling per split. Print one GROUP LABEL per item, in input order, separated by single spaces, under this rule:

• item 1 is always in group 1
• each later item is either in a group that some earlier item already uses, or
• in the next unused group number, and never in a higher one

That is the only labelling of a split obeying the rule, so two different lines are always two different splits, and no de-duplication is ever needed. Lines are printed in LEXICOGRAPHIC order, compared position by position, which is exactly what trying the labels in increasing order at every item produces.

## The method

go(i, used): if i == n: record cur; return for lab in 1 .. min(used + 1, k): cur.push(lab); go(i + 1, max(used, lab)); cur.pop()

Compare it with #1192 and exactly two things are gone: the used == k test at the end, and both of the bounds. The bounds are gone because there is nothing left to be short of. Every prefix extends to at least one answer, since the remaining items can always join group 1, so no branch is ever dead and no pruning is possible or needed.

## Why it is correct

Identical to #1192: the rule-obeying labellings are in one-to-one correspondence with the splits, and the search generates each one once. The only difference is which of them are accepted, and here it is all of them whose largest label is at most k, which the loop bound min(used + 1, k) already guarantees, so the accept test is unconditional.

## The settled boundaries

The answer is never empty: putting every item in group 1 uses one group, and k is at least 1, so that split is always allowed. So none is never printed. k = 1 gives exactly one line and k at least n gives the full Bell number. Both ends are tested.

## Cost

One node per rule-obeying prefix with no label above k, and every leaf is an answer, so the search does no wasted work at all. The output is the cost: 203 lines at n = 6.

Constraints - `1 ≤ k ≤ n ≤ 6`