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

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


Try it online!

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


# 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 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 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 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 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 at 7:00 • Ah yep I figured as much. May 18 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 at 7:55 • @AidenChow let's take this to chat May 18 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 at 6:46 • Thank you! @AidenChow May 18 at 7:01 # Factor + math.combinatorics math.unicode, 37 bytes [ all-subsets [ Σ ] map duplicates ]  Try it 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).

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

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

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

# 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 at 6:54
• sum(1for ... if sum(k)==sum(l)) can be sum(sum(k)==sum(l)for ...) May 16 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 at 16:15
• @AndyB True, totally missed that. Thank you for your effort. May 17 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.


# C (clang), 131 bytes

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


This leaks horribly. Try it online!

# 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