# Find the fairest partition of a list

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.

## Examples:

[1,2,3]       -> 0  # [1,2], 
[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], 
[1,3,9,27]    -> 14 # [1,3,9], 


## Rules

• 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

• Suggest [2,2,2,3,3] -> 0
– att
Nov 5 at 9:40
• You say absolute values of the sums, but the sums are always positive. Do you mean the absolute value of the difference? Nov 5 at 17:48
• "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 [2.5.7.3.11] or [17,19,13,23], etc. Nov 5 at 18:35
• @DewiMorgan I clarified that the ordering should be independent of the numbers in the list, does this fix the problem Nov 6 at 7:05
• @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. Nov 6 at 17:32

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

### How?

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

æOÂαß


## Explanation

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

f=\(x,s=0)if(any(x),f(x[-1],c(s,-s)+x),min(abs(s)))


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

\(x)min(abs((1:max(s<-2^seq(x))%o%(2/s)%/%1%%2*2-1)%*%x))


Attempt This Online!

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

Thanks to @Giuseppe for saving three bytes!

• 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. Nov 5 at 18:32
• @Giuseppe, thanks, good spot Nov 5 at 19:26

# JavaScript (Node.js), 55 bytes

f=([c,...x],y=0)=>c?1/Math.max(1/f(x,y+c),1/f(x,y-c)):y


Try it online!

-1B from tsh

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

# Jelly, 7 bytes

żNŒp§AṂ


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:

ŒP§ạU$Ṃ ŒP§ḤạSṂ LØ+ṗ×⁸§AṂ  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 } }  • 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} Nov 5 at 16:29 # Vyxalg, 31 bitsv2, 3.875 bytes ṗṠḂε  Try it Online! Bitstring: 1001111110100111110010001110010  Ports 05ab1e exactly, command for command. ## Explained ṗṠḂε­⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁢⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁣⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁤⁪‏‏​⁡⁠⁡‌⁢⁡​‎‏​⁢⁠⁡‌­ ṗ # ‎⁡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 /↧⌵-⇌.≐(/+▽)⋯⇡ⁿ⧻,2  Try it! /↧⌵-⇌.≐(/+▽)⋯⇡ⁿ⧻,2 ⁿ⧻,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 ŋ∑Aaṁ  Attempt This Online! A port of @att's K (ngn/k) answer. ŋ∑Aaṁ ŋ 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. • Porting ovs's Uiua answer instead gives 14 bytes [:<./[:|(+,-)/. Nov 6 at 7:34 • Nice, I had played around with that but was over-complicating it. Nov 6 at 7:46 • [:|(+,-)/ -> (+|@,-)/ – 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! • – l4m2 Nov 5 at 10:01 • for i in s: for j in l: l=l+[i+j] -> for i in s:l+=[i+j for j in l]. And change to set could be better. ato – tsh Nov 6 at 6:05 # 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 Ｘ Raised to power θ Input list Ｌ Length Ｅ Map over implicit range θ Input list Ｅ Map over elements λ Current element × Multiplied by ι Outer value ÷ Integer divided by ² Literal integer 2 Ｘ Raised to power μ Inner index ﹪ Modulo ² Literal integer 2 Σ Take the sum ⊗ Doubled ↔ Vectorised absolute ⌊ Take the minimum Ｉ 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:  ⁻Σθ⊗ＥＸ²Ｌθ As above θ Input list × Zipped multiply with κ Current value ↨ Converted to base ² Literal integer 2 ↨¹ Take the sum Ｉ⌊↔ 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: ⌊/|(+/i×m)-+/(i←(b,n)⍴v)×~m←⍉(n⍴2)⊤⍳b←2*n←⍴v←⎕  Try it online! Thanks to Dyalog Classic # Jelly, 7 bytes ŒṖ§ḅ-AṂ  A monadic Link that accepts a list of integers and yields the smallest partition difference. Try it online! ### How? 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 [[,,],[,[5,6]],[[4,5],],[[4,5,6]]] § - sums [[4,5,6],[4,11],[9,6],] ḅ- - 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  Alternatives Œ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

=LET(
a,A1#,
b,ROWS(a),
c,MOD(INT(SEQUENCE(2^b,,)/2^SEQUENCE(,b,)),2),
MIN(ABS(MMULT(c,a)-MMULT(ABS(1-c),a)))
)


Input is spilled, vertical array in cell A1.

# C (GCC), 66 bytes

A,B;d(a,n)int*a;{for(A=B=0;n--;)A<B?A+=a[n]:(B+=a[n]);a=abs(A-B);}


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.
• 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. Nov 5 at 17:04
• Note that this algorithm fails for [2,2,2,3,3] anyway. Nov 5 at 17:12
• -3 bytes: A,B;d(a,n)int*a;{for(A=B=0;n--;*(A<B?&A:&B)+=a[n]);a=abs(A-B);} Nov 5 at 20:34

# Desmos, 86 bytes

f(l)=[abs(l.total-2total(mod(floor(2i/{2^{[1...L]}),2)l))fori=[1...2^L]].min
L=l.count


Try It On Desmos!

Try It On Desmos! - Prettified