There's more than one way to skin a set

Given a set of positive integers $$\ S \$$, output the set of all positive integers $$\ n \$$ such that $$\ n \$$ can be made by summing a subset of $$\ S \$$ in more than one different way, i.e., that are the sums of more than one subset of $$\ S \$$.

To be clear, a subset of $$\ S \$$ means that you can't use numbers from $$\ S \$$ more than once.

Example

For example, given $$\ S = \{2, 3, 5, 6\} \$$, the following numbers can be made:

• $$\ 2 = \sum\{2\} \$$
• $$\ 3 = \sum\{3\} \$$
• $$\ 5 = \sum\{5\} = \sum\{2, 3\} \$$
• $$\ 6 = \sum\{6\} \$$
• $$\ 7 = \sum\{2, 5\} \$$
• $$\ 8 = \sum\{2, 6\} = \sum\{3, 5\} \$$
• $$\ 9 = \sum\{3, 6\} \$$
• $$\ 10 = \sum\{2, 3, 5\} \$$
• $$\ 11 = \sum\{5, 6\} = \sum\{2, 3, 6\} \$$
• $$\ 13 = \sum\{2, 5, 6\} \$$
• $$\ 14 = \sum\{3, 5, 6\} \$$
• $$\ 16 = \sum\{2, 3, 5, 6\} \$$

Of these, only $$\ 5 \$$, $$\ 8 \$$, and $$\ 11 \$$ can be made in more than one way. Therefore, [5, 8, 11] is the output.

Rules

• The input will be non-empty and contain no duplicate numbers
• Output may be in any order, but it must not contain duplicate numbers
• You may use any standard I/O method
• Standard loopholes are forbidden
• This is , so the shortest code in bytes wins

Test cases

[1]                   -> []
[4, 5, 2]             -> []
[9, 10, 11, 12]       -> [21]
[2, 3, 5, 6]          -> [5, 8, 11]
[15, 16, 7, 1, 4]     -> [16, 20, 23, 27]
[1, 2, 3, 4, 5]       -> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]


BQN, 15 bytesSBCS

(1=⊒)⊸/·⥊(∾∾+)˝


Run online!

BQN, 19 bytesSBCS

(1=⊒)⊸/<+´∘×¨⟜⥊⟜↕2¨


Run online!

2¨ A 2 for each value in the input array.
↕ Indices of an array of shape 2 × ... × 2. These are all combinations of 0's and 1's of the length of the input.
⥊ Flatten into a list of lists.
< ×¨ Multiply each of the indices with the input element-wise.
+´ Take the sum of each result.
(1=⊒)⊸/ Keep only elements which occur the second time.

Wolfram Language (Mathematica), 34 33 bytes

Set@@@Gather[Tr/@Subsets@#]⋃{}&


Try it online!

             Tr/@Subsets@#      subset sums
Gather[             ]     group by value
Set@@@                          drop first per group and join
⋃{}  union (unique)


In normal usage, Set is just assignment, e.g. Set[a,1] ~ a=1, returning the assigned value. Importantly,

• It always returns that assigned value, even when the assignment target is invalid, and
• When called with ≠2 arguments, it reasonably interprets that as assigning a target to a Sequence of the remaining arguments, i.e. Set[a,1,2] ~ a=Sequence[1,2].
(On a side note, Mathics does not do this, possibly because Set already has SequenceHold)

Together, these mean that Set can (usually) replace ##2& to save one byte.

R, 66 bytes

\(S,t=table(unlist(Map(\(i)combn(S,i,sum),seq(!S)))))names(t[t>1])

Attempt This Online!

Vyxal, 8 bytes

ṗṠsĠ~Ḣvh


sĠ~Ḣvh is the shortest way I can think of to keep only duplicates, so...

~Ḣvh could alternatively be vḢfU for same byte count.

How?

ṗṠsĠ~Ḣvh
ṗ        # Powerset of (implicit) input
Ṡ       # Sum of each
s      # Sort
Ġ     # Group consecutive identical items
~    # Filter for:
Ḣ   #  Remove the head (this means if it is only one item long, it will be falsey, else truthy)
vh # Get the first item of each


JavaScript (V8), 69 bytes

a=>(g=([v,...a],s=0)=>v?g(a,s+v)|g(a,s):(g[s]=-~g[s])-2||print(s))(a)


Try it online!

Commented

a => (              // a[] = input array
g = (             // g is a recursive function taking:
[v,             //   v = next value
...a],      //   a[] = remaining values
s = 0           //   s = sum
) =>              //
v ?               // if v is defined:
g(a, s + v) |   //   do a recursive call where v is added to s
g(a, s)         //   do a recursive call where s is left unchanged
:                 // else:
(g[s] = -~g[s]) //   using g as an object, increment a counter for
//   the sum s
-2 ||           //   if this is the 2nd time we reach this sum:
print(s)      //     print it
)(a)                // initial call to g


J, 28 19 bytes

[:~.@(#~1-~:)(,,+)/


Try it online!

-9 thanks to ovs for the (,,+)/ trick for calculating all subset sums!

• (,,+)/ All subset sums
• [:(#~1-~:) Keep only repeats
• ~.@ Dedup
• I think 1#.]#~2#:@i.@^# can simply be (,,+)/. (The order of the output is different)
– ovs
May 16, 2022 at 9:20
• Yes! I think I've used that trick before but had forgot about it. It's a good one, thanks. May 16, 2022 at 11:38

Jelly, 8 bytes

ŒP§œ-Q$Q  Try it online! How it works ŒP§œ-Q$Q - Main link. Takes S on the left
ŒP       - Powerset of S
§      - Sum of each
$- To the list of sums: Q - Deduplicate œ- - Set difference Q - Deduplicate  • Exactly what I had! May 15, 2022 at 17:04 Desmos, 96 bytes n=L.length S=[total(floor(mod(i/2^{[0...n]},2))L)fori=[0...2^n-1]].sort f(L)=S[S[2...]=S].unique  Try it on Desmos! How it works Conceptually similar to Steffan's Vyxal solution but lacks builtins :) S=[total(floor(mod(i/2^{[0...n]},2))L)fori=[0...2^n-1]].sort for i=[0...2^n-1] # Powerset of input as bitmasks total(floor(mod(i/2^{[0...n]},2))L) # Sum of each .sort # Sort f(L)= S[ ] # Filter for: S[2...]=S # Next element is equal to current element .unique # Remove duplicates  Note on the slice comparison: S[2...] is the list S except for the first element. Since broadcasting takes the shorter list, S[2...]=S is equivalent to S[2...n]=S[1...n-1], or [{S[i+1] = S[i]} for i=[1...n-1]] = 1. • Oh wow this is a smart solution (especially the S[S[2...]=S] part, ingenious!), I didn't think about doing it this way. May 18, 2022 at 5:57 • @AidenChow that's allowed. Same as when a language uses an int type and can't handle 2^32 as an intermediate value. It's just a lower limit than other languages. May 18, 2022 at 7:00 • Ah yep I figured as much. May 18, 2022 at 7:11 • Also unrelated to your answer but how do i get argmin and argmax to work? It is not working for me for some reason. May 18, 2022 at 7:55 • @AidenChow let's take this to chat May 18, 2022 at 7:56 Attache, 33 bytes ${{_~x>1}\Unique@x}##Sum=>Subsets


Try it online!

Happy 1,000 answers on this site to me?

Explanation

${{_~x>1}\Unique@x}##Sum=>Subsets pure function Subsets get all Subsets Sum=> and map Sum to each subset ## then${                }                  x = the set of subsets sums
Unique@x                   get those unique sums
{     }\                           and filter each sum
_~x                               ...by counting how often it appears in x
>1                             ...and asserting it is more than 1


Other approaches

Unfortunately, while there are a few builtins which have similar behavior, wrangling them into a manageable format proves to be too verbose.

50 bytes: Flat@Betail@{Commonest[_,1:#_]^^nil}##Sum=>Subsets

39 bytes: ${{_&Count!x>1}\Unique@x}##Sum=>Subsets 38 bytes: First=>{_@1@1}\Positions##Sum=>Subsets 37 bytes: @&0=>{_@1@1}\Positions##Sum=>Subsets • Congrats on 1000 answers! May 18, 2022 at 6:46 • Thank you! @AidenChow May 18, 2022 at 7:01 PARI/GP, 48 bytes a->[k-1|c<-Vec(prod(i=!k=0,#a,1+x^a[i])),c>#k++] Attempt This Online! Using generating functions. For input $$\\{a_1,\dots,a_n\}\$$, finds all $$\k\$$s such that the coefficient of $$\x^k\$$ in $$\\prod_{i=1}^n(1+x^{a_i})\$$ is greater than $$\1\$$. Factor + math.combinatorics math.unicode, 37 bytes [ all-subsets [ Σ ] map duplicates ]  Try it online! Python, 79 75 bytes -4 bytes thanks to pxeger! def f(a,*o): for x in a: for d in*o,0:o.count(v:=x+d)==1!=print(v);o+=v, Attempt This Online! Python 2, 102 bytes Much longer, but more fun ;) (and much faster) s=1;p=0 for x in input(): r=s&s<<x&~p|p<<x&~s;p|=r;s|=s<<x;k=0 while r: if r%2:print k r/=2;k+=1 Attempt This Online! Haskell, 120 bytes g(s,d)i=(i:s,if ielems&&inotElemd then i:d else d) f c=snd.foldl g([],[])$map(sum.zipWith(*)c)(sequence[[0,1]|_<-c])


Try it online!

• g :: ([Int], [Int]) -> Int -> ([Int], [Int]) is a straightforward function which keeps track of all 'seen' integers in the first list in the tuple, and all 'duplicates' in the second list.

• sequence [[0,1] | _ <- c] generates the Cartesian product of n copies of [0, 1], where n is the length of the input, i.e. it generates all permutations of 0 and 1 with length n.

• map (sum . zipWith (*) c) takes the dot product of each of these permutations with the input, which generates all possible sums (plus a stray zero, which is inconsequential, since the input is positive).

SageMath, 123 bytes

Golfed vesrion. Run it on SageMathCell!

def f(a):return[k for k,m in enumerate(prod(1+PolynomialRing(QQ,'x').gen()^b for b in a).coefficients(sparse=False))if m>1]


Ungolfed vesrion. Run it on SageMathCell!

def find_ks(a):
# Create a polynomial ring
R = PolynomialRing(QQ, 'x')
x = R.gen()

# Calculate the generating function
gen_function = prod(1 + x^a_i for a_i in a)

# Find the coefficients of the generating function
coeffs = gen_function.coefficients(sparse=False)

# Iterate over the coefficients and return the k-values for which the coefficients are greater than 1
ks = [k for k, coeff in enumerate(coeffs) if coeff > 1]

return ks

input_lists = [[1], [4, 5, 2], [9, 10, 11, 12], [2, 3, 5, 6], [15, 16, 7, 1, 4], [1, 2, 3, 4, 5]]

for a in input_lists:
print(f"{a} -> {find_ks(a)}")


Using generating functions. For input $$\\{a_1,\dots,a_n\}\$$, finds all $$\k\$$s such that the coefficient of $$\x^k\$$ in $$\\prod_{i=1}^n(1+x^{a_i})\$$ is greater than $$\1\$$.

Burlesque, 12 bytes

R@)++JNB\\NB


Try it online!

R@     # All subsequences
)++    # Map sum
J      # Dup
NB     # Remove duplicates
\\     # List elements in set A not in B
NB     # Remove duplicates


Python 3, 106 bytes

g=lambda s:{s}|{q for n in s for q in g(s-{n})}
def f(s):*q,=map(sum,g(s));*map(q.remove,{*q}),;return{*q}


Try it online!

Requires a frozenset as input.

05AB1E, 7 bytes

æOÐ¢≠ÏÙ


Or alternatively:

æO{Åγ≠Ï


Explanation:

æ        # Get the powerset of the (implicit) input-list
O       # Sum each inner list
Ð      # Triplicate it
¢     # Pop the top two, and get the counts of each item
≠    # Check which counts are NOT 1 (thus >= 2)
Ï   # Only keep those values from the remaining list
Ù  # Uniquify it
# (after which the result is output implicitly)

æO       # Same as above
{      # Sort them
Åγ    # Pop and run-length encode this list, pushing the list of values and
# list of counts as two separated lists
≠Ï  # Same as above
# (after which the result is output implicitly)


Brachylog, 13 bytes

⊇ᶠ+ᵐ{⊇Ċ=}ᶠhᵐd


Try it online!

Explanation

⊇ᶠ               Find all subsets of the input
+ᵐ             Compute the sum for each of these subsets
{   }ᶠ       Find all:
⊇Ċ=           Subset of 2 elements which are equal
hᵐ     Get the head of each of these subsets
d    Remove duplicates (necessary if 3 or more subsets sum to the same number)


There are other similar approaches which are also 13 bytes, such as ⊇ᶠ+ᵐọ{t>1&h}ˢ or ⊇ᶠ+ᵍ{l>1&h+}ˢ.

Desmos, 148 bytes

L=[∑_{n=1}^{2^{l.length}-1}bfori=[0...l.total]]
b=\{\total(l\mod(\floor(2n/{2^{[l.\length...1]}}),2))=i,0\}
K=[0...L.\length]\{L>1,0\}
f(l)=K[K>0]


Try It On Desmos!

Try It On Desmos! - Prettified

Charcoal, 21 bytes

⊞υ⁰ＦＡＦ⁺υι⊞υκＩΦ⌈υ‹¹№υι


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

⊞υ⁰


Start with 0 as the sum of the empty subset of S.

ＦＡ


Loop over the elements of S.

Ｆ⁺υι⊞υκ


Add the element to all of the existing sums and append the results.

ＩΦ⌈υ‹¹№υι


Output the values that occur more than once.

Python 3.8, 152 bytes

-5 bytes thanks to ovs, -4 bytes thanks to pxeger, and -2 bytes thanks to AndyB

Outputs a set of numbers or an empty set() if the condition is not met.

lambda s:(r:=range(len(s)))and{T(l)for j in r for l in c(s,j+1)if T(T(k)==T(l)for i in r for k in c(s,i+1))>1}
from itertools import*;c=combinations;T=sum


Attempt This Online!

• from itertools import*;c=combinations saves two bytes and len([k for ...]) -> sum(1for ...).
– ovs
May 16, 2022 at 6:54
• sum(1for ... if sum(k)==sum(l)) can be sum(sum(k)==sum(l)for ...) May 16, 2022 at 7:21
• You can save 2 more bytes by writing from itertools import*;c=combinations;T=sum and replacing sum(...) with T(...). May 17, 2022 at 16:15
• @AndyB True, totally missed that. Thank you for your effort. May 17, 2022 at 17:13

Japt, 12 bytes

à mx ü lÉ câ


Try it

Zsh, 75 bytes

for i;a=({$i,}+0$^a)
for s ($a)((++S[s])) for s ("$S[@]")((++k,s>1))&&<<<$k  Try it online! Accidentally out-golfed my old power set implementation, whoops! :) for i a=({$i,}+0$^a) # Recursively generate sum strings (e.g.: +0+02+0+04) for s ($a)
((++S[s]))           # Count how many times a sum occurs
for s ("$S[@]") ((++k,s>1))&&<<<$k   # If sum $k is bigger than 1, print$k.


T-SQL, 114 bytes

Using a table variable as input

WITH D(s,b)as(SELECT*FROM @
UNION ALL SELECT
S+Q,L
FROM @,D WHERE b<l)SELECT
s FROM D GROUP BY s HAVING SUM(1)>1


Try it online

(!!1)~<<bg<fo<<ss


Explanation

• ss get all subsequences
• fo sum them
• bg group like elements
• (!!1) get the second element from each group

(!!1)~<<bg appeared in this answer previously as a way to get all elements that appear more than once.

Reflection

(!!) should have a prefix function, and a bunch of versions with the index prefilled. I noticed this earlier but still didn't fix it, and now it's coming back to haunt me.

Well guess what, I still haven't fixed it, and it's still losing me bytes.

On top of that the fact that I've used the exact same code (!!1)~<<bg now in two different answers is probably a good indicator that it should receive a standalone function.

Arturo, 58 bytes

\$=>[powerset&|map=>sum|tally|select[k,v]->v>1|map[k,v]->k]


Try it

Stax, 14 bytes

ü÷┬┼╔ª8┐b▼¶╦S╟


Run and debug it

definitely golfable, cant seem to find any way to right now

unpacked:

Stax, 16 bytes

S{|+mX{x#1=!fu|u


Run and debug it

S{|+mX{x#1=!fu|u # whole program taking input array S
S                # powerset of S
{  m            # across this powerset, map...
|+             # sum
{     f    # and filter it by
X x#        # the count of the element in the summed powersets
=!     # is not equal to
1       # 1
u   # uniquify
|u # uneval, produces string representation of array (no idea if this is required or not, otherwise stax outputs the array as an array of charcodes)


C (clang), 131 129 123 bytes

saved 2 bytes thanks to @ceilingcat

*c,i,j;f(*a,n){for(i=n,j=1;i--;)c=calloc(j+=a[i],8);for(i=n*j,*c=1;j;)i?c[i%j+a[i/j]]+=c[--i%j]:c[--j]>1&&printf("%d ",j);}
`

This leaks horribly. Try it online!