16
\$\begingroup\$

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], [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]

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

Improve this question
\$\endgroup\$
5
  • 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 [2.5.7.3.11] or [17,19,13,23], etc. \$\endgroup\$
    – Dewi Morgan
    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\$
    – Dewi Morgan
    Nov 6 at 17:32

19 Answers 19

Reset to default
11
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
10
\$\begingroup\$

05AB1E, 7 5 bytes

æOÂαß

Attempt this online! or try all testcases

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
Improve this answer
\$\endgroup\$
7
\$\begingroup\$

K (ngn/k), 16 bytes

&//|/-:\+/:/+-:\

Try it online!

            +-:\    ± each
        +/:/        outer sum
   |/-:\            abs
&//                 min
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
5
\$\begingroup\$

R, 56 bytes

f=\(x,s=0)`if`(any(x),f(x[-1],c(s,-s)+x[1]),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!

Improve this answer
\$\endgroup\$
2
  • 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\$
    – Nick Kennedy
    Nov 5 at 19:26
5
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
  • \$\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
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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
  }
}
Improve this answer
\$\endgroup\$
1
  • \$\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
3
\$\begingroup\$

Vyxal g, 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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • 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
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
3
  • \$\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
0
\$\begingroup\$

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

Improve this answer
\$\endgroup\$

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.