# Split a list into maximal equal-sum sections

Given a non-empty list of positive digits, group them into sublists of equal sum. You may output any subset of solutions with maximal number of sublists (equivalently, minimal sum).

The input may contain repeat elements. There may not exist any solution but the singleton list containing the input itself. The output does not need to be in any particular order. You may not assume in the input list is in any particular order.

## Format

You must accept a non-empty list of positive integers and output a 2D list of those integers, both in any reasonable format. Since I have restricted the inputs to 1-9, you may just accept a string of digits as input. However, your output give an obvious indication as to how the sublists are split.

## Test Cases

These only show one solution, but if more exist, you may output them instead, or multiple, etc.

[9, 5, 1, 2, 9, 2]        ->  [[9, 5], [1, 2, 9, 2]]
[1, 1, 3, 5, 7, 4]        ->  [[1, 1, 5], [3, 4], [7]]
[2, 9, 6, 1, 5, 8, 2]     ->  [[2, 9], [6, 5], [1, 8, 2]]
[2, 8, 3, 9, 6, 9, 3]     ->  [[2, 3, 9, 6], [8, 9, 3]]
[5, 4, 1]                 ->  [[5], [4, 1]]
[3, 8, 1, 4, 2, 2]        ->  [[3, 1, 4, 2], [8, 2]]
[6, 9, 3, 8, 1]           ->  [[6, 3], [9], [8, 1]]
[4, 1, 6, 9, 1, 4, 5, 2]  ->  [[4, 1, 6, 1, 4], [9, 5, 2]]
[8, 7, 8, 6, 1]           ->  [[8, 7], [8, 6, 1]]
[2, 7, 4, 5]              ->  [[2, 7], [4, 5]]
[5, 2, 1, 4, 4]           ->  [[5, 2, 1], [4, 4]]
[5, 7, 4, 6, 2]           ->  [[5, 7], [4, 6, 2]]
[4, 1, 6, 6, 9]           ->  [[4, 9], [1, 6, 6]]
[2, 6, 4]                 ->  [[2, 4], [6]]
[6, 3, 1, 6, 8, 4, 5, 7]  ->  [[6, 3, 1, 6, 4], [8, 5, 7]]
[2, 2, 2]                 ->  [[2], [2], [2]]
[2, 4, 5]                 ->  [[2, 4, 5]]


Here is an extremely inefficient test case generator.

• Note: this question was in the Sandbox for only an hour and a half. I strongly discourage this. The only reason I posted this so soon was because I want to repcap and I am confident with a challenge this simple. It's best to leave it for at least 48 hours and until you have sufficient upvotes or positive feedback. Commented May 31, 2021 at 19:14
• Why did you want to repcap so badly?
– user
Commented May 31, 2021 at 19:15
• @user m̶y̶ ̶g̶o̶a̶l̶s̶ ̶a̶r̶e̶ ̶b̶e̶y̶o̶n̶d̶ ̶y̶o̶u̶r̶ ̶u̶n̶d̶e̶r̶s̶t̶a̶n̶d̶i̶n̶g̶ badge progress Commented May 31, 2021 at 19:15
• So these are multisets rather than lists?
– Neil
Commented May 31, 2021 at 20:09
• @Neil I suppose that'd be more accurate, since you can reorder the numbers however you want. Commented May 31, 2021 at 20:10

# J, 65 bytes

<@/:~((i.~/:~@;&.>)>@{])[:(\:#&>)@,@(g/.~+/&>)g=:<@#~"#.2#:@i.@^#


Try it online!

A different approach to brute force. All test cases execute in a few seconds on TIO.

Consider 2 7 4 5...

• g=:<@#~"#.2#:@i.@^# Generate all subsets of the input, and save the verb that does this as g so we can use it again later.

┌┬─┬─┬───┬─┬───┬───┬─────┬─┬───┬───┬─────┬───┬─────┬─────┬───────┐
││5│4│4 5│7│7 5│7 4│7 4 5│2│2 5│2 4│2 4 5│2 7│2 7 5│2 7 4│2 7 4 5│
└┴─┴─┴───┴─┴───┴───┴─────┴─┴───┴───┴─────┴───┴─────┴─────┴───────┘

• (g/.~+/&>) Group subset elements by sum, and for each group of same-sum elements, generate all of its subsets:

┌┬─────────┬─────┬───────────┐
││┌┐       │     │           │
││││       │     │           │
││└┘       │     │           │
├┼─────────┼─────┼───────────┤
││┌─┐      │     │           │
│││5│      │     │           │
││└─┘      │     │           │
├┼─────────┼─────┼───────────┤
││┌─┐      │     │           │
│││4│      │     │           │
││└─┘      │     │           │
├┼─────────┼─────┼───────────┤
││┌───┐    │┌───┐│┌───┬───┐  │
│││2 7│    ││4 5│││4 5│2 7│  │
││└───┘    │└───┘│└───┴───┘  │
├┼─────────┼─────┼───────────┤
││┌───┐    │┌─┐  │┌─┬───┐    │
│││2 5│    ││7│  ││7│2 5│    │
││└───┘    │└─┘  │└─┴───┘    │
├┼─────────┼─────┼───────────┤
││┌───┐    │     │           │
│││7 5│    │     │           │
││└───┘    │     │           │
├┼─────────┼─────┼───────────┤
etc...

• [:(\:#&>)@,@ Flatten, and sort down by length:

┌─────────┬───────┬───────────┬──┬───┬───┐
│┌───┬───┐│┌─┬───┐│┌───┬─────┐│┌┐│┌─┐│┌─┐│
││4 5│2 7│││7│2 5│││7 4│2 4 5││││││5│││4││ ...etc..
│└───┴───┘│└─┴───┘│└───┴─────┘│└┘│└─┘│└─┘│
└─────────┴───────┴───────────┴──┴───┴───┘

• <@/:~((i.~/:~@;&.>)>@{]) Find the first one whose elements match those of the input, and open it:

┌───┬───┐
│4 5│2 7│
└───┴───┘

• Very nice! May not be the golfiest, but I always appreciate solutions that take a less brute-force approach to problems that offer a straightforward solution. Commented Jun 1, 2021 at 4:40
• For reference, porting this to Jelly comes to 21 bytes Commented Jun 1, 2021 at 22:45
• @cairdcoinheringaahing Nice. Jelly generally seems to clock in at about half or 40% of J from unscientific occasional noticing, so that's good compression. One of these days I'll learn Jelly.... Commented Jun 1, 2021 at 22:47
• The "generate all subsets" bit is definitely Jelly's main byte saver over J here tbh. ŒP does in 2 bytes what you assign to g. If J had a powerset builtin, this would be pretty close to Jelly in length Commented Jun 1, 2021 at 22:49
• Also, if/when you do want to start Jelly, feel free to drop by Jelly Hypertraining :) Commented Jun 1, 2021 at 22:54

# Jelly, 13 bytes

Œ!ŒṖ€Ẏ§E$ƇLÐṀ  Try it online! Very slow, works on $$\O(2^{n!})\$$ complexity, where $$\n\$$ is the length of the array. Times out for anything with $$\n \ge 8\$$ on TIO. This feels too long, especially the Œ!ŒṖ€Ẏ bit to generate all possible partitions. This outputs all possible solutions, but the TIO link (the ÇḢ bit in the Footer) limits it to just one ## How it works Œ!ŒṖ€Ẏ§E$ƇLÐṀ - Main link. Takes a list L on the left
Œ!            - All permutations of L
ŒṖ€         - Get all partitions of each permutation
Ẏ        - Drop these down into a single list of 2d lists
$Ƈ - Keep those for which the following is true: § - Sums of each sublist E - Are all equal LÐṀ - Get those with a maximal length  • Only replacement I can think of for Œ!ŒṖ€Ẏ is JṗL¹ƙ€, which comes out a byte longer if you account for chaining, but it doesn't feel impossible that there's something along those lines that would work. Commented May 31, 2021 at 22:53 • This is still a byte longer, but does get rid of the LÐṀ... Commented May 31, 2021 at 23:18 # 05AB1E, 12 bytes œ€.œ€éR.ΔOË  Try it online! œ # all permutations of the input €.œ # for €ach permutation, get each partition € # flatten by one level to get a list of many partitions é # sort by length (number of sublists in a partition) R # reverse, longest are now at the front .Δ # find the first partition where ... OË # ... each sublist sums to the same value  # Brachylog, 12 bytes ∧≜S&p~c.+ᵛS∧  Try it online! Even less efficient than caird's Jelly solution, as it recomputes every partition of every permutation for each sum it tries.  ~c. Output a partition of &p a permutation of the input +ᵛ in which every sublist has the same sum, ∧≜S S∧ which is as small as possible.  # JavaScript (ES6), 124 bytes f=(a,n=1)=>(g=(a,q=[],b=[],s=n)=>s?a.some((x,i)=>g(a.filter(_=>i--),q,[...b,x],s-x)):!a[Q=[...q,b],0]||g(a,Q))(a)?Q:f(a,n+1)  Try it online! ### Commented f = ( // f is a recursive function taking: a, // a[] = input list n = 1 // n = target sum, starting with 1 ) => ( // g = ( // g is a recursive function taking: a, // the original a[] or a subset of it q = [], // q[] = list of sublists b = [], // b[] = current sublist s = n // s = n minus the sum of the terms in b[] ) => // s ? // if s is not equal to 0: a.some((x, i) => // for each value x at index i in a[]: g( // do a recursive call to g: a.filter(_ => i--), // remove the i-th element from a[] q, // pass q[] unchanged [...b, x], // append x to b[] s - x // subtract x from s ) // end of recursive call ) // end of some() : // else: !a[ Q = [...q, b], // Q[] = copy of q[] with b[] appended 0 // test whether a[] is empty ] || // if it's not: g(a, Q) // recursive call to g with q[] = Q[] )(a) ? // initial call to g; if a solution is found: Q // return it : // else: f(a, n + 1) // try again with n + 1  # Ruby, 110 109 107 bytes ->l,*r{1.step.find{|x|l.permutation.find{|c|w=-1;r=c.chunk{|z|(w+=z)/x}.map &:last;r.all?{|v|v.sum==x}}};r}  Try it online! ### How: • Starting with x=1, check if we can split the list into chunks whose sum is x. • Do the same check with every possible permutation of the list. • If not, increase x and try again. • The trick is here: c.chunk{|z|(w+=z)/x}. This function splits an array into smaller # Wolfram Language (Mathematica), 145 bytes (l=Length@#;Catch[Do[If[SameQ@@Total/@(t=TakeList[p,i]),Throw@t],{d,Reverse@Divisors@Total@#},{i,IntegerPartitions[l,{d}]},{p,Permutations@#}]])&  Try it online! Rough compromise between speed/memory optimization and code-golf. The following facts are used: • Array can only be splitted by the number of parts that are dividing its sum • The lengths of parts of any split must be integer partition of length of array Of course, one can optimize the search much better (for example, the dividers of the sum of the array must be less than its length), but it lengthens the code. On the other hand, I don’t want to take away given optimization, because it reduces runtime significantly. # Scala, 773 bytes $$\\text{773 bytes, it can be golfed much more.}\$$ Golfed version. Try it online! def findX(list: List[Int]): Option[List[List[Int]]] = { @tailrec def findXRec(x: Int): Option[List[List[Int]]] = { list.permutations.collectFirst { case perm if { val chunks = perm.foldRight(List.empty[List[Int]]) { case (z, acc) => if (acc.isEmpty || acc.head.sum + z > x) List(z) :: acc else (z :: acc.head) :: acc.tail } chunks.forall(_.sum == x) } => perm } match { case Some(perm) => { Some(perm.foldRight(List.empty[List[Int]]) { case (z, acc) => if (acc.isEmpty || acc.head.sum + z > x) List(z) :: acc else (z :: acc.head) :: acc.tail }) } case None => findXRec(x + 1) } } findXRec(1) }  Ungolfed version. Try it online! import scala.annotation.tailrec object Main { def main(args: Array[String]): Unit = { println(findX(List(9, 5, 1, 2, 9, 2))) println(findX(List(1, 1, 3, 5, 7, 4))) println(findX(List(2, 9, 6, 1, 5, 8, 2))) println(findX(List(2, 2, 2))) println(findX(List(2, 4, 5))) } def findX(list: List[Int]): Option[List[List[Int]]] = { @tailrec def findXRec(x: Int): Option[List[List[Int]]] = { val permutations = list.permutations val validPartition = permutations.collectFirst { case perm if { var w = -1 val chunks = perm.foldRight(List.empty[List[Int]]) { case (z, acc) => if (acc.isEmpty || acc.head.sum + z > x) List(z) :: acc else (z :: acc.head) :: acc.tail } chunks.forall(_.sum == x) } => perm } validPartition match { case Some(perm) => { var w = -1 Some(perm.foldRight(List.empty[List[Int]]) { case (z, acc) => if (acc.isEmpty || acc.head.sum + z > x) List(z) :: acc else (z :: acc.head) :: acc.tail }) } case None => findXRec(x + 1) } } findXRec(1) } }  # Nekomata, 10 bytes O:ᵐ∑≡$Ðaṁl


Attempt This Online!

O:ᵐ∑≡$Ðaṁl O Non-deterministically choose a set partition of the input : Duplicate ᵐ∑ Sum each ≡ Check if all sums are equal, and get the equal value$Ð         Pair the sum with the partition
a        Get all possible values
ṁ       Minimum (by the sum)
l      Take the last element (the partition)


# Julia 1.7 + Combinatorics, 74 bytes

using Combinatorics
~x=argmin(p->keys(sum.(p)∪0)=>sum.(p),partitions(x))


Attempt This Online!

argmin(f, itr) needs julia 1.7 or later