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

28 Answers 28

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

\$\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, 2022 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, 2022 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, 2022 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, 2022 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, 2022 at 7:00
  • \$\begingroup\$ Ah yep I figured as much. \$\endgroup\$
    – Aiden Chow
    May 18, 2022 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, 2022 at 7:55
  • \$\begingroup\$ @AidenChow let's take this to chat \$\endgroup\$ May 18, 2022 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, 2022 at 6:46
  • \$\begingroup\$ Thank you! @AidenChow \$\endgroup\$ May 18, 2022 at 7:01
3
\$\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\$
2
\$\begingroup\$

Factor + math.combinatorics math.unicode, 37 bytes

[ all-subsets [ Σ ] map duplicates ]

Try it online!

\$\endgroup\$
2
\$\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
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\$

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

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

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

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

Haskell + hgl, 17 bytes

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

If you click on the linked answer you can see in that answer I said:

(!!) 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.

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

Arturo, 58 bytes

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

Try it

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

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

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!

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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