List array elements which can be summed from other elements

Question

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 code-golf, 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.

Answer 1

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

Answer 2

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

Answer 3

Haskell, ⁴⁹ 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!

Answer 4

Scala, ⁴⁶ 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

Answer 5

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.

Answer 6

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!

Answer 7

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)

Answer 8

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.

Answer 9

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.

Answer 10

Charcoal, 44 30 bytes

crossed out 44 is still regular 44

ＦＥＸ²ＬθΦθ﹪÷ιＸ²μ²Ｆ№⁻⁻θυιΣι⊞υΣιＩυ

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

ＦＥＸ²ＬθΦθ﹪÷ιＸ²μ²

Loop over all possible subsets of the input.

Ｆ№⁻⁻θυιΣι

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.

Ｉυ

Output all the results.

Answer 11

Stax, 9 bytes

ïΩ▀▼ø▄GÉ.

Run and debug it

idea borrowed from caird's answer.

Answer 12

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

Answer 13

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.

Answer 14

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!

Answer 15

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

Answer 16

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.