Given a list of positive integers, partition the list into two sublists such that the absolute value of the difference of the sums over the two sublists is minimal.
The output of the program should be the (non-negative) difference of these sums.


[1,2,3]       -> 0  # [1,2], [3]
[2,3,5,7,11]  -> 0  # [2,5,7], [3,11]
[13,17,19,23] -> 0  # [13,23], [17,19]
[1,2,3,4]     -> 0  # [1,4], [2,3]
[2,2,2,3,3]   -> 0  # [2,2,2], [3,3]
[1,2,3,4,5]   -> 1  # [1,2,4], [3,5]
[1,2,3,4,5,6] -> 1  # [1,2,3,4], [5,6]
[1,1,2,5]     -> 1  # [1,1,2], [5]
[1,3,9,27]    -> 14 # [1,3,9], [27]


  • The sublists do not need to be contiguous
  • Every element of the list has to be in (exactly) one of the two sublists
  • The list can contain duplicate elements
  • You can assume that the list contains at least 3 elements
  • You are allowed to assume that the list is sorted (using any convenient ordering)
  • The ordering of two numbers should be the same for all lists
  • This is the shortest solution wins

related challenge

  • 1
    \$\begingroup\$ Suggest [2,2,2,3,3] -> 0 \$\endgroup\$
    – att
    Nov 5 at 9:40
  • 1
    \$\begingroup\$ You say absolute values of the sums, but the sums are always positive. Do you mean the absolute value of the difference? \$\endgroup\$
    – Luis Mendo
    Nov 5 at 17:48
  • 2
    \$\begingroup\$ "Any convenient ordering", eh? Seems like the most convenient would be one which is ascending until the necessary split, like, from the examples, [3,1,2] or [] or [17,19,13,23], etc. \$\endgroup\$ Nov 5 at 18:35
  • 1
    \$\begingroup\$ @DewiMorgan I clarified that the ordering should be independent of the numbers in the list, does this fix the problem \$\endgroup\$
    – bsoelch
    Nov 6 at 7:05
  • \$\begingroup\$ @bsoelch That's a really weird phrasing, since I can't think of any way to sort numbers in a list without using the numbers in the list. \$\endgroup\$ Nov 6 at 17:32

19 Answers 19


Python, 57 bytes

f=lambda A,B,*a:min((z:=[abs,f][a>()])(A+B,*a),z(A-B,*a))

Attempt This Online!

Takes splatted input. Input must have at least 2 elements.


Recursively builds up all possible differences by successively adding or subtracting each element (except the first which is allowed to break symmetry).


05AB1E, 7 5 bytes


Attempt this online! or try all testcases


Utilizes the fact that 05AB1E's powerset builtin returns the sets in the same order as looking at the numbers \$0\$ - \$2^n-1\$ in binary reversed, so the opposite of each element when reversing is its complement.

æ        # all subsets of the input
O        # the sum of each
        # Bifurcated, push the reverse without popping
α        # take the absolute difference (vectorizes)
ß        # the minimum of that

K (ngn/k), 16 bytes


Try it online!

            +-:\    ± each
        +/:/        outer sum
   |/-:\            abs
&//                 min

Uiua, 10 bytes

Same idea as loopy walt's Python answer.


Try it!

/↧⌵/(⊂⊃+-)  # Function taking a vector from the stack and leaving a number
   /(    )  # Reduce the vector by ...
     ⊂      # Concatenate the results from ...
      ⊃+-   # both adding and subtracting the new value from all intermediate values.
  ⌵         # Take the Absolute Value of each number
/↧          # Reduce by Minimum

R, 56 bytes


Attempt This Online!

A recursive function, partly inspired by @loopywalt’s Python answer so be sure to upvote that one too! Takes an integer vector and returns an integer.

An alternative non-recursive approach R, 60 57 bytes


Attempt This Online!

This one avoids recursion, but uses an outer multiplication table and matrix multiplication.

Thanks to @Giuseppe for saving three bytes!

  • 1
    \$\begingroup\$ I think you can get the non-recursive version down using %o% instead of outer but I'm on mobile and getting the parentheses just right is a nightmare. \$\endgroup\$
    – Giuseppe
    Nov 5 at 18:32
  • \$\begingroup\$ @Giuseppe, thanks, good spot \$\endgroup\$ Nov 5 at 19:26

JavaScript (Node.js), 55 bytes


Try it online!

-1B from tsh

  • \$\begingroup\$ f=([c,...x],y=0)=>c?1/Math.max(1/f(x,y+c),1/f(x,y-c)):y \$\endgroup\$
    – tsh
    Nov 6 at 5:51

Jelly, 7 bytes


Try it online!

A monadic link that takes a list of integers and returns an integer. Works by zipping the original list with its negation, taking the Cartesian project, and finding the minimum absolute sum.

Alternative 7-byters and a 9-byter:


The first two are variants on @CommandMaster’s 05AB1E answer. The third works similarly to my non-recursive R answer. Note the TIO link above includes all 4 versions.


Scala, 98 82 bytes

Saved 16 bytes thanks to @corvus_192

Golfed version. Try it online!

def?(l:Seq[Int],y:Int=0):Int=l match{case c::x=> ?(x,y+c)min?(x,y-c)case _=>y.abs}

Ungolfed version. Try it online!

object Main {
  def f(list: List[Int], y: Int = 0): Int = {
    list match {
      case c :: x => math.min(f(x, y + c), f(x, y - c))
      case Nil    => math.abs(y)

  def main(args: Array[String]): Unit = {
    println(f(List(1,2,3)))         // -> 0
    println(f(List(2,3,5,7,11)))    // -> 0
    println(f(List(13,17,19,23)))   // -> 0
    println(f(List(1,2,3,4)))       // -> 0
    println(f(List(1,2,3,4,5)))     // -> 1
    println(f(List(1,2,3,4,5,6)))   // -> 1
    println(f(List(1,1,2,5)))       // -> 1
    println(f(List(1,3,9,27)))      // -> 14
  • \$\begingroup\$ 82 bytes: def?(l:Seq[Int],y:Int=0):Int=l match{case c::x=> ?(x,y+c)min?(x,y-c)case _=>y.abs} \$\endgroup\$
    – corvus_192
    Nov 5 at 16:29

Vyxal g, 31 bitsv2, 3.875 bytes


Try it Online!



Ports 05ab1e exactly, command for command.


ṗ     # ‎⁡Powerset, in infinite list friendly order
 Ṡ    # ‎⁢Vectorised sums
  Ḃ   # ‎⁣Bifurcated
   ε  # ‎⁤Absolute differences
# ‎⁢⁡The g flag returns the smallest item. 

Created with the help of Luminespire.


Uiua, 18 bytes


Try it!

              ⁿ⧻,2  # 2 to the <length of input> power
             ⇡      # create a range from that number
            ⋯       # binary (vectorizing big-endian)
      ≐(   )        # tribute (apply (...) to each binary list and the input)
          ▽         # keep (forming an element of the power set of the input)
        /+          # sum
     .              # duplicate (the sums)
    ⇌               # reverse
  ⌵-                # absolute difference
/↧                  # minimum

Nekomata, 5 bytes


Attempt This Online!

A port of @att's K (ngn/k) answer.

ŋ       Optionally negate each element of the input
 ∑      Sum
  A     Absolute value
   a    All possible values
    ṁ   Minimum

J, 14 13 bytes


Try it online!

A port of ovs's Uiua answer thanks to Bubbler. -1 thanks to att.

J, 18 bytes


Try it online!

A port of att's nice K answer.

  • 1
    \$\begingroup\$ Porting ovs's Uiua answer instead gives 14 bytes [:<./[:|(+,-)/. \$\endgroup\$
    – Bubbler
    Nov 6 at 7:34
  • \$\begingroup\$ Nice, I had played around with that but was over-complicating it. \$\endgroup\$
    – Jonah
    Nov 6 at 7:46
  • 1
    \$\begingroup\$ [:|(+,-)/ -> (+|@,-)/ \$\endgroup\$
    – att
    Nov 6 at 8:14

Python, 86 bytes

-10 bytes by l4m2
-4 bytes thanks to tsh

def f(s,l={0}):
 for i in s:l|={i+j for j in l}
 return min(abs(a+a-sum(s))for a in l)

First time golfing in Python!

Attempt This Online!


Charcoal, 24 20 bytes


Try it online! Link is to verbose version of code. Explanation: Port of @mathscat's Python answer.


Start with the sum of the empty sublist.


Loop over the input list.


Calculate the sums of the subsets including the current element and any subset of the previous elements and append those to the list of subset sums.


Calculate the minimum difference between each subset and its complement, using the equation \$ | \sum (U \setminus A) - \sum A | = | \sum U - \sum A - \sum A | = | \sum U - 2 \sum A | \$.

Previous 24-byte solution:


Try it online! Link is to verbose version of code. Explanation:

     θ                      Input list
    Σ                       Take the sum
   ⁻                        Vectorised subtract
         ²                  Literal integer `2`
        X                   Raised to power
           θ                Input list
          L                 Length
       E                    Map over implicit range
              θ             Input list
             E              Map over elements
                λ           Current element
               ×            Multiplied by
                   ι        Outer value
                  ÷         Integer divided by
                     ²      Literal integer `2`
                    X       Raised to power
                      μ     Inner index
                 ﹪          Modulo
                       ²    Literal integer `2`
            Σ               Take the sum
      ⊗                     Doubled
  ↔                         Vectorised absolute
 ⌊                          Take the minimum
I                           Cast to string
                            Implicitly print

19 bytes using the newer version of Charcoal on ATO:


Attempt This Online! Link is to verbose version of code. Explanation:

   ⁻Σθ⊗EX²Lθ        As above
               θ    Input list
              ×     Zipped multiply with
                 κ  Current value
                ↨   Converted to base
                  ² Literal integer `2`
            ↨¹      Take the sum
I⌊↔                 As above

(Sum doesn't work on empty lists because it needs to know what type of list it's summing.)


APL+WIN, 46 bytes

Prompts for vector of integers:


Try it online! Thanks to Dyalog Classic


Jelly, 7 bytes


A monadic Link that accepts a list of integers and yields the smallest partition difference.

Try it online!


Creates all partitions then treats every other part as being in the first of the two sets. Calculates the difference by converting the sums of the parts from base one (which takes the negative of every other part-sum).

ŒṖ§ḅ-AṂ - Link: list of integers  e.g. [4,5,6]
ŒṖ      - all list partitions          [[[4],[5],[6]],[[4],[5,6]],[[4,5],[6]],[[4,5,6]]]
  §     - sums                         [[4,5,6],[4,11],[9,6],[15]]
   ḅ-   - from base -1                 [5,7,-3,15] i.e. 6-5+4=5 11-4=7 6-9=3 15=15
     A  - absolute values              [5,7,3,15]
      Ṃ - minimum                      3


ŒP§ạṚ$Ṃ - sum every subset absolute difference with its own reverse, minimum
żNŒp§AṂ - zip with negative, take the Cartesian product, get sums, absolute values, minimum

Excel, 106 bytes


Input is spilled, vertical array in cell A1.


C (GCC), 66 bytes


Attempt This Online!

-1 thanks to Arnauld.

A simple greedy algorithm.

The program uses a wide assortment of tricks:

  • K&R function declarations
  • Assumes that the input is sorted, per challenge specs.
  • Global variables assumed zero & permitted to omit the type specifier due to implicit int.
  • Implicit int in function declaration
  • ~i will check if i is not -1.
  • Ternary operator replaces an if.
  • A return statement is avoided by assuming -O0 and exploiting the load to a writing to rax, the return value register on x86.
  • \$\begingroup\$ Functions must be reusable and you cannot simply assume that A and B are reset to 0 between 2 calls. But you can save some bytes by getting rid of i, so I think this should work for 66 bytes. \$\endgroup\$
    – Arnauld
    Nov 5 at 17:04
  • 4
    \$\begingroup\$ Note that this algorithm fails for [2,2,2,3,3] anyway. \$\endgroup\$
    – Arnauld
    Nov 5 at 17:12
  • \$\begingroup\$ -3 bytes: A,B;d(a,n)int*a;{for(A=B=0;n--;*(A<B?&A:&B)+=a[n]);a=abs(A-B);} \$\endgroup\$
    – corvus_192
    Nov 5 at 20:34

Desmos, 86 bytes


Try It On Desmos!

Try It On Desmos! - Prettified


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.