Split a list into maximal equal-sum sections

Question

Task

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.

Answer 1

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│
  └───┴───┘
  

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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.

Answer 8

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)
  }
}

Answer 9

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)

Answer 10

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