1195. Every Split Into k Groups Under a Cap

Each of n items carries a weight, which may be zero. Print every way to put the items into exactly k groups where no group weighs more than m.

Problem #1194 demanded the group totals be EQUAL. This demands only that each one stay under a ceiling, and the difference is larger than it looks: an equal split is pinned to a single value computed from the total, so the prune and the accept test collapse into one, while a cap leaves a range of legal totals and the two have to be kept apart.

weights 1 2 3 4, k = 2, cap 5 1 2 2 1 groups weigh 5 and 5 only that one, because any other two-group split puts 3 and 4 together or leaves one group above 5

## What most people try first

Enumerate every split into k groups and filter. The filter is cheap and the enumeration is not: S(n, k) splits at n = 8, k = 4 is 1701, and a tight cap can leave none of them standing. The work is spent before the test is reached.

## 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: if used == k: record cur return if used + (n - i) < k: return for lab in 1 .. min(used + 1, k): if sum[lab] + w[i] > m: continue sum[lab] += w[i]; cur[i] = lab go(i + 1, max(used, lab)) sum[lab] -= w[i]

The accept test is used == k and nothing more, which is sound for a reason worth stating plainly: the prune refuses to create any group over the cap, so every group alive at depth n is already under it. Checking the cap again at the leaf would never fail. That is a different argument from #1194, where the equality was deduced from the arithmetic; here it is simply that the invariant was maintained all the way down.

## Why the prune is sound

Weights are non-negative, so a group's total never decreases as items join it. A group already above m is therefore above m in every descendant of that node, and no leaf below it is an answer. Zero weights are the case to think about: they can be added freely without changing any total, which means a cap of 0 is satisfiable exactly when every weight is 0, and the smallest test checks it.

## The settled boundaries

k = n puts every item alone, so it is legal when every single weight is at most m. k = 1 is legal when the whole total is at most m, and the two single-group tests sit either side of that line with the same weights and caps of 6 and 5. When nothing is legal the program prints none.

## Cost

One node per prefix the cap admits. A loose cap admits everything, so the worst case is the full S(n, k) enumeration plus O(n) per answer printed. A tight cap can cut the tree to almost nothing, which is the whole reason to test inside the recursion rather than after it.

Constraints - `1 ≤ k ≤ n ≤ 8` - `0 ≤ w[i] ≤ 100` - `0 ≤ m ≤ 1000`