14
\$\begingroup\$

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]
\$\endgroup\$
0

24 Answers 24

8
\$\begingroup\$

BQN, 15 bytesSBCS

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

Run online!


BQN, 19 bytesSBCS

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

Run online!

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.

\$\endgroup\$
7
\$\begingroup\$

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)
\$\endgroup\$
5
\$\begingroup\$

R, 66 bytes

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

Attempt This Online!

\$\endgroup\$
5
\$\begingroup\$

Vyxal, 8 bytes

ṗṠsĠ~Ḣvh

Try it online or run all test cases.

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
  • 2
    \$\begingroup\$ I think 1#.]#~2#:@i.@^# can simply be (,,+)/. (The order of the output is different) \$\endgroup\$
    – ovs
    May 16 at 9:20
  • \$\begingroup\$ Yes! I think I've used that trick before but had forgot about it. It's a good one, thanks. \$\endgroup\$
    – Jonah
    May 16 at 11:38
3
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Exactly what I had! \$\endgroup\$
    – pxeger
    May 15 at 17:04
3
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Oh wow this is a smart solution (especially the S[S[2...]=S] part, ingenious!), I didn't think about doing it this way. \$\endgroup\$
    – Aiden Chow
    May 18 at 5:57
  • \$\begingroup\$ @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. \$\endgroup\$ May 18 at 7:00
  • \$\begingroup\$ Ah yep I figured as much. \$\endgroup\$
    – Aiden Chow
    May 18 at 7:11
  • \$\begingroup\$ Also unrelated to your answer but how do i get argmin and argmax to work? It is not working for me for some reason. \$\endgroup\$
    – Aiden Chow
    May 18 at 7:55
  • \$\begingroup\$ @AidenChow let's take this to chat \$\endgroup\$ May 18 at 7:56
3
\$\begingroup\$

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

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Congrats on 1000 answers! \$\endgroup\$
    – Aiden Chow
    May 18 at 6:46
  • \$\begingroup\$ Thank you! @AidenChow \$\endgroup\$ May 18 at 7:01
2
\$\begingroup\$

Factor + math.combinatorics math.unicode, 37 bytes

[ all-subsets [ Σ ] map duplicates ]

Try it online!

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

Haskell, 120 bytes

g(s,d)i=(i:s,if i`elem`s&&i`notElem`d 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).

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

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

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

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

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.

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

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!

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

05AB1E, 7 bytes

æOТ≠ÏÙ

Try it online or verify all test cases.

Or alternatively:

æO{Åγ≠Ï

Try it online or verify all test cases.

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)
\$\endgroup\$
1
\$\begingroup\$

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+}ˢ.

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

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

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

Charcoal, 21 bytes

⊞υ⁰FAF⁺υι⊞υκIΦ⌈υ‹¹№υι

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

⊞υ⁰

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

FA

Loop over the elements of S.

F⁺υι⊞υκ

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

IΦ⌈υ‹¹№υι

Output the values that occur more than once.

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

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!

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

Japt, 12 bytes

à mx ü lÉ câ

Try it

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

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.
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

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