1198. Every Split Into k Groups of Equal Size

Print every way to put n items into exactly k groups that all hold the same number of items.

4 items, k = 2 each group holds 2 1 1 2 2 {1,2} and {3,4} 1 2 1 2 {1,3} and {2,4} 1 2 2 1 {1,4} and {2,3} three of them, which is 4! / (2! * 2! * 2!)

## What most people try first

Enumerate every split into k groups and keep those whose groups have matching sizes. At n = 8, k = 4 that filters 1701 splits down to 105, so six out of seven nodes are wasted, and the waste is avoidable: a group that already holds more than n / k items can never shrink.

Before any of that, settle the arithmetic. If n is not a multiple of k there is no answer at all, because k equal sizes add to a multiple of k. That one test disposes of a whole class of inputs without a single recursive call.

## 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

size = n / k 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 count[lab] == size: continue # that group is already full count[lab] += 1; cur[i] = lab go(i + 1, max(used, lab)) count[lab] -= 1

As in #1194 the accept test says nothing about sizes, and for the same kind of reason: no group is ever allowed past size, there are k groups, and they hold n = k * size items between them, so each holds exactly size. The counting bound stays because it is cheap and still fires.

## Why it is correct, counted two ways

The search generates each rule-obeying labelling with equal group sizes exactly once, which is one answer per split. Independently, the number of such splits has a closed form: choose the groups as an ordered sequence of disjoint size-subsets, n! / (size!)^k ways, then divide by k! because the groups are unordered. So the answer count is

n! / ( (size!)^k * k! )

At n = 8, k = 4 that is 40320 / (2^4 * 24) = 105, and at n = 6, k = 3 it is 720 / (2^3 * 6) = 15. Two methods agreeing is what makes the expected outputs here trustworthy rather than merely reproducible.

## The settled boundaries

k = 1 is one group of n, always legal, exactly one answer. k = n is n singletons, always legal, exactly one answer. When n is not a multiple of k the answer is empty and the program prints none, which is tested at 4 3.

## Cost

One node per prefix no group has overfilled, which is a factor of about k! below the unfiltered split count at the sizes here, plus O(n) to print each answer.

Constraints - `1 ≤ k ≤ n ≤ 8`