1194. Every Split Into k Groups of Equal Total

Each of n items carries a positive weight. Print every way to put the items into exactly k groups whose weights add to the same total.

weights 1 2 3 4, k = 2 total 10, so each group must weigh 5 1 2 2 1 {1,4} weighs 5 and {2,3} weighs 5 nothing else works, so one line is the whole answer

## What most people try first

Enumerate every split into k groups, then keep the ones whose group totals agree. That is correct and it is also the whole problem left undone: the number of splits is the Stirling number S(n, k), which at n = 8, k = 4 is 1701 and at n = 12, k = 6 is 1323652, while the number that survive the filter is usually tiny or zero. Almost all the work is spent building splits that are already doomed.

The doom is visible early. Weights are positive, so a group's total only ever rises as items join it. The moment a group passes the required total, every split below that point in the search is dead, and there can be a great many of them.

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

First settle feasibility with arithmetic rather than search. Let T be the sum of all the weights. If T is not a multiple of k there is no answer at all, because k equal totals must add to a multiple of k. Otherwise the required total is target = T / k.

go(i, used): if i == n: if used == k: record cur return if used + (n - i) < k: return # cannot still reach k groups for lab in 1 .. min(used + 1, k): if sum[lab] + w[i] > target: continue # this group is full sum[lab] += w[i]; cur[i] = lab go(i + 1, max(used, lab)) sum[lab] -= w[i]

Notice what the accept test does NOT say. It does not check that the totals are equal. It does not have to: the prune guarantees every group total is at most target, there are k of them, and together they hold weight T = k * target. A set of k numbers each at most target summing to k * target has every one of them exactly target. So reaching depth n with k groups open is already a proof that the totals agree.

## Why the prune is sound

A group's total never falls, because weights are positive and an item is never removed from a group once the recursion has placed it below that point. So if the total is already above target, no deeper assignment can bring it back down, and no leaf under that branch can be an answer. Skipping the branch therefore removes no answers.

## The settled boundaries

k = 1 always has exactly one answer, the single group, because its total is T and target is T. k = n has an answer only when every weight is the same. When T is not a multiple of k the answer is empty and the program prints none; that case is tested twice, once where the totals could never match and once where they are close but not reachable.

## Cost

One node per prefix the prune admits, which on the inputs here is far below S(n, k) and on an adversarial input is equal to it. No bound can do better than that in general, since deciding whether even one such split exists is the multi-way partition problem.

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