22
\$\begingroup\$

Consider an array of unique integers, with an arbitrary length greater than 2. It is sometimes possible to express elements of the array as the sum of at least two other elements. For example, if our array is [2, 3, 1], we can express 3 as the sum 2+1. However, we can't express either 2 or 1 as the sum of other elements.

Additionally, each integer in the list may only be used once in each sum. For example, with [1, 2, 5] we can't express 5 as 2+2+1 (or 1+1+1+2 etc.) as we can only use each element once per sum.

Your program should take such array as input, via any convenient method, and output the elements of the input that are expressible as the sum of other elements. The output may be in any order, as may the input.

This is , so aim to make your code as short as possible, time / space complexity be damned.

Test cases

input -> output
[2, 3, 1] -> [3]
[8, 2, 1, 4] -> []
[7, 2, 1, 4] -> [7]
[7, 2, 1, 4, 6] -> [6, 7]
[0, 1, -1] -> [0]
[4, 2, -2, 0] -> [2, 0]
[0, 1, 2] -> []

Explanation for the last test case and result: For the purposes of this problem statement, zero cannot be considered the sum of a resulting empty list. Zero can only be in the resulting list IFF two or more other elements of the input list can be added to sum to it.

In other words, do not assume that if 0 is in the input, it should always be in the output - you cannot choose an empty subset to cover it. The problem statement explicitly states that any element in the resulting list must be the sum of other elements.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Also, in general here we prefer to score in bytes not characters, because characters leads to a lot of loopholes. I would recommend switching to this way for normal code-golf. \$\endgroup\$
    – Wheat Wizard
    May 21 '21 at 15:20
  • 12
    \$\begingroup\$ time / space complexity be damned : Yeah! That's the code golf spirit! :-p \$\endgroup\$
    – Arnauld
    May 21 '21 at 15:37
  • 1
    \$\begingroup\$ Why is the output for [0, 1, -1] not [0, 1 -1]? I can get 0 from 1 + -1, I can get 1 from 0 + 1, and I can get -1 from 0 + -1. \$\endgroup\$
    – chunes
    May 21 '21 at 16:20
  • 2
    \$\begingroup\$ @UnrelatedString The input is an array of unique integers. \$\endgroup\$
    – Arnauld
    May 21 '21 at 22:59
  • 3
    \$\begingroup\$ I've reopened this challenge but the clarifying changes have made nearly every answer invalid. I will delete my own invalid answer, but leave it up to others determine which answers are or are not valid, and inform their owners. If an answer is invalid and it's owner does not choose to delete it in a reasonable timeframe from being informed please flag it for moderator attention and we will handle it. \$\endgroup\$
    – Wheat Wizard
    May 23 '21 at 18:27

16 Answers 16

6
\$\begingroup\$

05AB1E, 7 bytes

ʒKæ¦Oyå

Try it online!

ʒ       # keep numbers of the input where:
 K      # the input with the number removed
  æ     # all subsets of this
   ¦    # remove the first subset (the empty list)
    O   # the sums of the subsets
     yå # contain the current number
\$\endgroup\$
3
  • \$\begingroup\$ Wow, looks like this will be the one to beat. Even for esolangs, this is impressive. \$\endgroup\$
    – root
    May 22 '21 at 15:26
  • 3
    \$\begingroup\$ This fails for inputs such as [0, 1, 2], per the recent question update. Should be fixable for 1 extra byte \$\endgroup\$ May 23 '21 at 19:02
  • \$\begingroup\$ 7 bytes, handles the zero case [0, 1, 2] fine now, unbeaten for a while and unlikely to be beaten. Accepted, great going! \$\endgroup\$
    – root
    May 23 '21 at 22:55
6
\$\begingroup\$

Jelly, 9 bytes

ɓḟŒPḊ§iµƇ

Try it online!

Essentially, we go over each element, x, of the input, L, and keep it if:

  • We remove x from the input, call that L'
  • We then get all non-empty subsets of L', and get the sums of each
  • Finally, if x is in these sums, we keep it

If 0 is not considered the sum of the empty list, then +1 byte

How it works

ɓḟŒPḊ§iµƇ - Main link. Takes a list L on the left
ɓ      µ  - Group the links between ɓ and µ into a dyad f(L, x):
 ḟ        -   Remove x from L, L'
  ŒP      -   Powerset of L'
    Ḋ     -   Remove the leading empty array
     §    -   Sums of each
      i   -   Index of x, or 0 if not present
        Ƈ - For each element, x, of L, keep it if f(L, x) is true
\$\endgroup\$
2
  • \$\begingroup\$ instead of filtering out sublists with zeroes, would it work to filter out the zeroes in the beginning? \$\endgroup\$
    – Razetime
    May 21 '21 at 15:31
  • \$\begingroup\$ @Razetime I believe it'd still be 2 bytes, so no improvement :( \$\endgroup\$ May 21 '21 at 15:32
6
\$\begingroup\$

Haskell, 49 54 bytes

  • +5 bytes to comply with the latest clarifications.
f a=[x|x<-a,elem x.tail.map sum$mapM(\y->0:[y|y/=x])a]

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Unfortunately, this seems to fail for test cases involving zeroes. \$\endgroup\$
    – user
    May 21 '21 at 23:22
  • 1
    \$\begingroup\$ @user Arguably, 0 is the sum of the empty subarray. I'll wait for the author to clarify. \$\endgroup\$
    – Delfad0r
    May 21 '21 at 23:32
  • \$\begingroup\$ By my interpretation of the question, you need to find elements to add together, and for an input such as [0], there aren't any other elements that can be summed together to 0. However, I've asked the author to add a test case for that to clarify, and hopefully they agree that 0 is the sum of the empty subarray, because that lets me undelete my own answer. \$\endgroup\$
    – user
    May 22 '21 at 0:27
5
\$\begingroup\$

Scala, 46 64 bytes

Fixed the zero problem thanks to Eric Duminil.

s=>s.filter(x=>(s-x).subsets.filter(_.nonEmpty)exists(_.sum==x))

Try it in Scastie!

Not super interesting. Takes and outputs Sets.

s =>  //The input, s
s.filter(x =>  //Keep only elements x that satisfy the following:
  (s-x).subsets  //The subsets of s with x removed
    .filter(_.nonEmpty) //Keep the ones that aren't empty
     exists(_.sum==x)) //Contain a Set whose sum is x
\$\endgroup\$
4
  • 2
    \$\begingroup\$ It's concise and readable, but it doesn't seem to output the correct result when 0 is included. :-/ \$\endgroup\$ May 24 '21 at 12:15
  • 1
    \$\begingroup\$ @EricDuminil Good catch, I'm fixing it now. I thought this one was immune to that but didn't realize that subsets also returned an empty set. \$\endgroup\$
    – user
    May 24 '21 at 13:09
  • 1
    \$\begingroup\$ im really sorry for the +18 bytes. I basically had the same problem in ruby. Concise or correct, but not both. :-/ \$\endgroup\$ May 24 '21 at 15:38
  • 2
    \$\begingroup\$ @EricDuminil It's nothing to be sorry about, you helped me fix my answer. Concise and invalid < less concise and correct :) \$\endgroup\$
    – user
    May 24 '21 at 17:51
5
\$\begingroup\$

Brachylog, 14 12 11 14 bytes

-1 thanks to Unrelated String; +3 due to rules clarification

{∋.;?↔x⊇,0Ṁ+}ᵘ

Try it online!

Explanation

{            }ᵘ  Find all unique outputs of this predicate:
 ∋.               The output is an element of the input list
   ;?              Pair the output with the input list
     ↔             Reverse (so we have [list, element])
      x            Remove that element from that list
       ⊇           Get an ordered subset of the remaining list
        ,0Ṁ        Append a 0 and assert that the list has at least 2 elements
                   (this excludes the empty subset from allowing a sum of 0)
           +       Sum that subset
                   That sum must also equal the output

Oddly, it seems that Brachylog doesn't have a builtin for "? = . is nonempty." I thought that ¬Ė might work, but it didn't.

\$\endgroup\$
3
  • \$\begingroup\$ ᶠd can be golfed to just . \$\endgroup\$ May 22 '21 at 5:07
  • \$\begingroup\$ This seems to produce the wrong output for the test case [0, 1, 2] (produces [0], should produce the empty list). Try it online! \$\endgroup\$ May 24 '21 at 1:57
  • \$\begingroup\$ @pppery Fixed. \$\endgroup\$
    – DLosc
    May 24 '21 at 16:50
4
\$\begingroup\$

JavaScript, 81 bytes

l=>l.filter((x,j)=>(g=(i,s)=>s==x||i in l&&(g(i+1,s)||j!=i&&g(i+1,~~s+l[i])))(0))

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ This seems to produce the wrong output for the [0, 1, 2] test case (produces [0], should produce the empty list). Try it online! \$\endgroup\$ May 24 '21 at 2:03
  • \$\begingroup\$ @pppery Fixed. Thanks. \$\endgroup\$ May 24 '21 at 2:13
3
\$\begingroup\$

R, 102 90 93 bytes

function(x)x[sapply(seq(x),function(n){for(i in seq(a<-x[-n]))F=F|x[n]%in%combn(a,i,sum);F})]

Try it online!

about -5 bytes thanks to @Dominic (needed little fix for 0-length sum, but waiting for clarification from OP)

\$\endgroup\$
5
  • 1
    \$\begingroup\$ 97 bytes usingsapply and [ instead of for and if... \$\endgroup\$ May 21 '21 at 23:05
  • \$\begingroup\$ If you use R 4.1 you can replace both functions with `` \$\endgroup\$ May 22 '21 at 13:50
  • \$\begingroup\$ @Nick Yeah, I know, but since it's not yet on TIO, I prefer not to use it. \$\endgroup\$
    – pajonk
    May 22 '21 at 14:45
  • \$\begingroup\$ @pajonk fair enough, though TIO is still on R 3.5.2 from 2018. \$\endgroup\$ May 22 '21 at 15:19
  • \$\begingroup\$ It's been a while since I used R, and I didn't know of these new features (even a pipe operator!). We should definitely ask to TIO maintainers to add R 4.1 ! \$\endgroup\$
    – digEmAll
    May 22 '21 at 20:03
3
\$\begingroup\$

J, 32 bytes

#~]e."p..1(+/@#~2#:@}.@i.@^#)\.]

Try it online!

Thanks to pppery for catching a subtle bug!

  • 1(...)\.] Take the 1 outfixes of the input (eg, outfixes of 1 2 3 are 2 3, 1 3, and 1 2)
  • +/@#~2#:@i.@^# For each, calculate all possible subset sums
  • ]e."p.. For each input number, is it an element of its corresponding outfix subset sum list?
  • #~ Filter the input by that answer.
\$\endgroup\$
2
  • \$\begingroup\$ This seems to produce the wrong output for the test case [0, 1, 2] (produces 0, should produce nothing). Try it online! \$\endgroup\$ May 24 '21 at 1:55
  • \$\begingroup\$ Thanks @pppery. Fixed now. The bug was because the sum +/ of the empty list in J is 0. Removing the subset associated with 0 fixed it. \$\endgroup\$
    – Jonah
    May 24 '21 at 2:34
3
\$\begingroup\$

Core Maude, 261 275 263 bytes

mod A is pr LIST{Int}*(sort List{Int}to L). op f : L -> L . op _,_ : L L ->
L . op _,_,_ : L L L ~> Bool . vars A B C D E : L . eq f(A)= A,nil . ceq
A B C,D = A C,D B if B,0,A C D . eq A,B = B[owise]. eq 0,1,A = true . ceq
A,B,C D E = true if A + - D,1,C E . endm

Example Session

             \||||||||||||||||||/
           --- Welcome to Maude ---
             /||||||||||||||||||\
         Maude 3.1 built: Oct 12 2020 20:12:31
         Copyright 1997-2020 SRI International
           Mon May 24 21:41:40 2021
Maude> mod A is pr LIST{Int}*(sort List{Int}to L). op f : L -> L . op _,_ : L L ->
> L . op _,_,_ : L L L ~> Bool . vars A B C D E : L . eq f(A)= A,nil . ceq
> A B C,D = A C,D B if B,0,A C D . eq A,B = B[owise]. eq 0,1,A = true . ceq
> A,B,C D E = true if A + - D,1,C E . endm
Maude> red f(2 3 1) .
reduce in A : f(2 3 1) .
rewrites: 20 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 3
Maude> red f(8 2 1 4) .
reduce in A : f(8 2 1 4) .
rewrites: 62 in 0ms cpu (0ms real) (62186 rewrites/second)
result L: nil
Maude> red f(7 2 1 4) .
reduce in A : f(7 2 1 4) .
rewrites: 55 in 0ms cpu (0ms real) (~ rewrites/second)
result NzNat: 7
Maude> red f(7 2 1 4 6) .
reduce in A : f(7 2 1 4 6) .
rewrites: 405 in 1ms cpu (2ms real) (203415 rewrites/second)
result NeList{Int}: 7 6
Maude> red f(0 1 -1) .
reduce in A : f(0 1 -1) .
rewrites: 32 in 0ms cpu (0ms real) (32096 rewrites/second)
result Zero: 0
Maude> red f(4 2 -2 0) .
reduce in A : f(4 2 -2 0) .
rewrites: 160 in 0ms cpu (0ms real) (~ rewrites/second)
result NeList{Int}: 2 0
Maude> red f(0 1 2) .
reduce in A : f(0 1 2) .
rewrites: 23 in 0ms cpu (0ms real) (~ rewrites/second)
result L: nil

Ungolfed

mod A is
    pr LIST{Int} * (sort List{Int} to L) .

    op f : L -> L .
    op _,_ : L L -> L .
    op _,_,_ : L L L ~> Bool .

    vars A B C D E : L .

    eq f(A) = A, nil .
    ceq A B C, D = A C, D B if B, 0, A C D .
    eq A, B = B [owise] .

    eq 0, 1, A = true .
    ceq A, B, C D E = true if A + - D, 1, C E .
endm

The answer is obtained by reducing the function f, which takes the list of integers. The helper function _,_ (one infix comma) separates "unprocessed" from "keep", and _,_,_ (two infix commas) decides if a given integer belongs in the output.

This question was actually pretty good for Maude (relatively speaking). Its matching engine can handle matching a list pattern like A B C (where A, B, and C are sublists) and trying all possible partitions.

I wasn't sure if I could accept input as a set rather than a list. If I could, I could save a few bytes because I could use set patterns like A, B (where A and B are subsets) and match with commutativity.


Added 12 bytes to handle the added requirement for 0, and also 2 bytes to fix a bug (forgot to pass D to t in the second equation).


Bought back 12 bytes by switching to a system module (fmod ... endfm to mod ... endm) and renaming f and t to _,_ and _,_,_ to save on parens and whitespace.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 44 30 bytes

crossed out 44 is still regular 44

FEX²LθΦθ﹪÷ιX²μ²F№⁻⁻θυιΣι⊞υΣιIυ

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

FEX²LθΦθ﹪÷ιX²μ²

Loop over all possible subsets of the input.

F№⁻⁻θυιΣι

See whether the sum is any of the elements of the input, not including the elements of the subset or sums found so far.

⊞υΣι

If so then remember this sum.

Iυ

Output all the results.

\$\endgroup\$
2
\$\begingroup\$

Stax, 9 bytes

ïΩ▀▼ø▄GÉ.

Run and debug it

idea borrowed from caird's answer.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 10 11 bytes

f}TsMty-QTQ

Test suite

+1 byte to account for the new test case

Explanation:
f}TsMty-QTQ | Full program
------------+------------------------------------------
f         Q | Filter the input for elements T such that
 }T         |  T is in
   sM       |   the sums of
      y     |    the powerset of
       -QT  |     the input with T removed
     t      |    with the empty set removed
\$\endgroup\$
1
\$\begingroup\$

Ruby, 73 bytes

->l{l.flat_map{|x|[x]&(l+l.map{0}-[x]).combination(l.size+2).map(&:sum)}}

Try it online!

If anybody finds another faling test, I am going to cry.

\$\endgroup\$
3
  • \$\begingroup\$ This produces the wrong output for the testcase [0,1,2] (should be the empty list, produces [1,2]). Try it online! \$\endgroup\$ May 24 '21 at 1:50
  • \$\begingroup\$ Thanks, should be fixed now \$\endgroup\$
    – G B
    May 24 '21 at 6:47
  • \$\begingroup\$ 0 breaks many concise, elegant answers. Your code fails for [4, 2, -2, 0]. \$\endgroup\$ May 24 '21 at 10:35
1
\$\begingroup\$

Python 2, 97 bytes

lambda L:L&{sum(y)for y in reduce(lambda r,x:r+[s+[x]for s in r],L,[[]])if len(filter(None,y))>1}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 38 bytes

Cases[Subsets@#,{a__}/;+a!=a:>+a]⋂#&

Try it online!

Relies on the input not having duplicates.

      Subsets@#                         subsets of input
Cases[         ,{a__}           ]         that are nonempty,
                     /;+a!=a              with a sum unequal to their elements
                            :>+a        get sums
                                 ⋂#     that are in input
\$\endgroup\$
0
\$\begingroup\$

Ruby, 80 bytes

->x{x.select{|y|(2...x.size).any?{|i|(x-[y]).combination(i).any?{|z|z.sum==y}}}}

Try it online!

This is still way too long and too readable. There must be a better way.

At least it seems to be one of the few answers which pass every test case.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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