Sign-Swapping Sums

Question

Given a nonempty list of positive integers \$(x, y, z, \dots)\$, your job is to determine the number of unique values of \$\pm x \pm y \pm z \pm \dots\$

For example, consider the list \$(1, 2, 2)\$. There are eight possible ways to create sums:

• \$+ 1 + 2 + 2 \to +5\$
• \$+ 1 + 2 − 2 \to +1\$
• \$+ 1 − 2 + 2 \to +1\$
• \$+ 1 − 2 − 2 \to −3\$
• \$− 1 + 2 + 2 \to +3\$
• \$− 1 + 2 − 2 \to −1\$
• \$− 1 − 2 + 2 \to −1\$
• \$− 1 − 2 − 2 \to −5\$

There are six unique sums \$\{5, -5, 1, -1, 3, -3\}\$, so the answer is \$6\$.

Test Cases

[1, 2] => 4
[1, 2, 2] => 6
[s]*n => n+1
[1, 2, 27] => 8
[1, 2, 3, 4, 5, 6, 7] => 29
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] => 45
[1, 7, 2, 8, 3, 1, 6, 8, 10, 9] => 56
[93, 28, 92, 100, 43, 66, 2, 98, 2, 52, 57, 75, 39, 77, 45, 15, 13, 82, 81, 20, 68, 14, 5, 3, 72, 56, 57, 1, 23, 25, 76, 59, 60, 71, 71, 24, 1, 3, 72, 84, 72, 28, 83, 62, 66, 45, 21, 28, 49, 57, 70, 3, 44, 47, 1, 54, 53, 56, 36, 20, 99, 9, 89, 74, 1, 14, 68, 47, 99, 61, 46, 26, 69, 21, 20, 82, 23, 39, 50, 58, 24, 22, 48, 32, 30, 11, 11, 48, 90, 44, 47, 90, 61, 86, 72, 20, 56, 6, 55, 59] => 4728

Reference solution (optimizes for speed and not size).

If you can't handle the last case because you use a brute-force method or similar, that's fine.

Scoring

This is code-golf, so the shortest valid solution (measured in bytes) wins.

Answer 1

Wolfram Language (Mathematica), 27 bytes

Tr[1^Fold[#⋃+##&,{0},#]]&

Try it online!

Finding the number of unique sign-swapping sums is equivalent to finding the number of unique subset sums.

A proof would involve adding the sum of the input to each of the sign-swapping sums and dividing by two. Then, there's an obvious bijection.

Explanation

Fold[#⋃+##&,{0},#]

Iterate through the input, with the initial value being {0}: take the union between <current value> and <current value> + input element (maps onto lists).

Tr[1^ ... ]

Golfy version of the Length function.

Answer 2

Jelly, 6 bytes

ŒPS€QL

Try it online!

Background

Let L be the input list and {P, N} a partition into algebraic summands with positive and negative signs. The challenge spec requires calculating s_{P,N} = sum(P) - sum(N).

However, since sum(P) + sum(N) = sum(L) and sum(L) does not depend on the partition, we have s_{P,N} = sum(P) - sum(N) = sum(P) - (sum(L) - sum(P)) = 2sum(P) - sum(L).

Thus, each unique value of sum(P) corresponds to one unique value of s_{P,N}.

How it works

ŒPS€QL  Main link. Argument: A (array)

ŒP      Powerset; generate all subarrays of A.
  S€    Take the sum of each.
    Q   Unique; deduplicate the sums.
     L  Take the length.

Answer 3

MATL, 11 10 bytes

nW:qBGY*un

Try it online! This is a port of Luis Mendo's Octave/MATLAB answer. I'm still trying to learn MATL, and I figured I'd post it, along with an explanation, since MATL is the language of the month.

Explanation:

Here's a read-through for anyone unfamiliar with stack based programming in general, and MATL in particular.

The input vector is implicitly placed on the stack. Note that when an operation is performed on an element in the stack, then that element is removed from the stack.

                % Stack:
                % [1, 2, 2]
n               % Counts the number of elements of the vector on the top of the stack.
                % Stack:
                % [3]
 W              % Raise 2^x, where x is the number above it in the stack
                % Stack:
                % [8]
  :             % Range from 1...x, where x is the number above it in the stack.                    % Stack:
                % [1, 2, 3, 4, 5, 6, 7, 8]
   q            % Decrement. Stack:
                % [0, 1, 2, 3, 4, 5, 6, 7]
    B           % Convert to binary. Stack:
                % [0,0,0; 0,0,1; 0,1,0; 0,1,1; 1,0,0; 1,0,1; 1,1,0; 1,1,1] 
     G          % Push input again. Stack:           
                % [0,0,0; 0,0,1; 0,1,0; 0,1,1; 1,0,0; 1,0,1; 1,1,0; 1,1,1], [1; 2; 2]
      Y*        % Matrix multiplication of the two elements on the stack.
                % Stack:
                % [0; 2; 2; 4; 1; 3; 3; 5]
        u       % Keep only unique elements. Stack:
                % [0; 2; 4; 1; 3; 5]
         n      % Number of elements in the vector. Stack:
                % [6]

And then it outputs the final element on the stack implicitly.

Answer 4

Python 2, 55 bytes

s={0}
for n in input():s|={t+n for t in s}
print len(s)

Try it online!

Answer 5

Python 2, 52 bytes

k=1
for n in input():k|=k<<n
print bin(k).count('1')

Try it online!

Uses the binary representation of a number to store the reachable subset sums.

Answer 6

05AB1E, 4 bytes

æOÙg

Utilizes the same approach used in Dennis’ Jelly answer.

Try it online!

Answer 7

R, 83 75 bytes

-8 bytes thanks to JayCe and Giuseppe

Creates a matrix of all possible combinations of (1,-1) for the size of the input vector, multiples this by the original vector to get the sums. Then unique and find the length of the result.

function(v)nrow(unique(t(t(expand.grid(rep(list(c(1,-1)),sum(v|1)))))%*%v))

---

previous version:

f=function(v)nrow(unique(as.matrix(expand.grid(rep(list(c(1,-1)),length(v))))%*%v))

Ungolfed with comments:

f=function(vector){

  List=rep(list(c(1,-1)),length(vector))   ## Create a list with length(vector) elements, all (1,-1)

  Combinations=expand.grid(Length)    ## get all combinations of the elements of the list, e.g, 1,-1,1,1,-1,1

  Matrix=as.matrix(Combinations)   ## convert to matrix

  Results=Matrix%*%vector   ## multiply the matrix original vector to get a Nx1 matrix

  Unique_results=unique(Results)   ## unique the results

  nrow(Unique_results)   ## length = number of rows of unique values
  }

Answer 8

Haskell, 46 bytes

import Data.List
length.nub.map sum.mapM(:[0])

Try it online!

Instead of summing the subsets of the input list, we make all combinations of either keeping a number or replacing it by 0, e.g.

mapM(:[0])[1,2,3] -> [[1,2,3],[1,2,0],[1,0,3],[1,0,0],[0,2,3],[0,2,0],[0,0,3],[0,0,0]]

This is two bytes shorter than subsequences.

Answer 9

Pari/GP, 39 bytes

a->#[1|n<-Vec(prod(i=1,#a,1+x^a[i])),n]

Counts the number of nonzero coefficients of the polynomial \$ \prod_{i \in a}(1+x^i) \$, where \$a\$ is the input.

Try it online!

Answer 10

Octave / MATLAB, 45 41 40 bytes

@(x)nnz(unique(dec2bin(0:2^nnz(x)-1)*x))

Input is a column vector (using ; as separator).

The code errors for the last test case due to memory restrictions.

This uses an idea from JungHwan Min's answer (subsets instead of alternating signs) to save a few bytes.

Try it online!

Answer 11

Python 3, 61 bytes

f=lambda a,s={0}:a and f(a[1:],s|{u+a[0]for u in s})or len(s)

Try it online!

Recursive approach, keeping track of unique subset sums.

The real fun is that this beats itertools by a big margin:

76 bytes

lambda a:len({*map(sum,product(*([0,x]for x in a)))})
from itertools import*

Try it online!

Answer 12

Pyth, 5 bytes

l{sMy

Utilizes the same approach used in Dennis’ Jelly answer.

Try it here.

Answer 13

APL (Dyalog Classic), 12 11 bytes

-1 thanks to H.PWiz

≢⊃(+∪⊢)/⎕,0

Try it online!

Answer 14

Attache, 29 bytes

{#Unique[Flat!±_]}@Fold[`±]

Try it online!

This works by folding the ± operator over the input list, then taking ± of that list, then counting the unique atoms of the array.

Here's some examples of how the folding works:

Fold[`±][ [1,2] ] == 1 ± 2
                  == [1 + 2, 1 - 2]
                  == [3, -1]
Fold[`±][ [1,2,2] ] == (1 ± 2) ± 2
                    == [3, -1] ± 2
                    == [[3 + 2, 3 - 2], [-1 + 2, -1 - 2]]
                    == [[5, 1], [1, -3]]
                    == [5, 1, 1, -3]
Fold[`±][ [4,4,4,4] ] == (4 ± 4) ± 4 ± 4
                      == [8, 0] ± 4 ± 4
                      == [[12, 4], [4, -4]] ± 4
                      == [[[16, 8], [8, 0]], [[8, 0], [0, -8]]]
                      == [16, 8, 8, 0, 8, 0, 0, -8]
                      == [16, 8, 0, -8]

Then we generate all permutations of the final sign by applying PlusMinus once more.

A more efficient version, 31 bytes

`#@(q:=Unique@Flat@`±)@Fold[q]

Try it online! This doesn't time out on the final test case, since it doesn't generate unnecessary combinations.

Answer 15

R, 62 bytes

function(V)sum(unique(c(V%*%combn(rep(0:1,L),L<-sum(V|1))))|1)

Try it online!

Ports Dennis' algorithm. It's closest to the Octave/MATL answers as it uses a similar bitmap and matrix product for inclusion/exclusion of terms.

Answer 16

Perl 5 -p, 39 bytes

s/^| /{+,-}/g;$_=grep!$s{eval$_}++,glob

Try it online!

Answer 17

JavaScript (ES6), 63 bytes

f=([c,...a],s=n=!(o={}))=>c?f(a,s-c)|f(a,s+c)&&n:o[s]=o[s]||++n

Try it online!

Answer 18

Husk, 5 bytes

LumΣṖ

Try it online!

Port of Dennis' Jelly answer.

Explanation

LumΣṖ                     [1,2,2]
    Ṗ  Powerset           [[],[1],[2],[1,2],[2],[1,2],[2,2],[1,2,2]]
  mΣ   Sum each           [0,1,2,3,2,3,4,5]
 u     Remove duplicates  [0,1,2,3,4,5]
L      Length             6

Answer 19

Perl 6, 33 bytes

{+set ([X](^2 xx$_)XZ*$_,)>>.sum}

Try it online!

Answer 20

Bash + GNU utilities, 49 bytes

eval echo "{,-}${@//,/{+,-\}}\;"|bc|sort -u|wc -l

Try it online!

Input given as a comma-separated list at the command-line.

Explanation

               ${@//,/{+,-\}}                      # Replace commas with {+,-}
          "{,-}${@//,/{+,-\}}\;"                   # Build a brace expansion with {+,-} before every number and ; at the end
eval echo "{,-}${@//,/{+,-\}}\;"                   # Expand to give every combination expression, separated by ;
                                |bc                # Arithmetically evaluate each line
                                   |sort -u        # Remove duplicates
                                            wc -l  # Count

Answer 21

C (gcc), 74 69 bytes

f(a,b)int*a;{long k=1;for(;b--;k|=k<<a[b]);a=__builtin_popcountl(k);}

Try it online!

C port of @xnor's answer

Answer 22

x86_64 machine language for Linux, 31 29 bytes

 0:   31 d2                   xor    %edx,%edx
 2:   6a 01                   pushq  $0x1
 4:   58                      pop    %rax
 5:   8b 0c 97                mov    (%rdi,%rdx,4),%ecx
 8:   48 89 c3                mov    %rax,%rbx
 b:   ff c2                   inc    %edx
 d:   48 d3 e3                shl    %cl,%rbx
10:   48 09 d8                or     %rbx,%rax
13:   39 d6                   cmp    %ese,%edx
15:   7c ee                   jle    5 <+0x5>
17:   f3 48 0f b8 c0          popcnt %rax,%rax
1c:   c3                      retq

Try it online!

Inspired by @xnor's answer. Requires a machine with the POPCNT instruction.

Answer 23

APL (Dyalog Classic), 34 33 32 bytes

{≢∪⍵+.×⍨↑{,⍵∘.,U}⍣(≢1↓⍵)⊢U←¯1 1}

Try it online!

Thanks to @ngn for -1 byte!

Answer 24

Clean, 82 bytes

import StdEnv
f[]=length
f[h:t]=f t o foldr(\e l=removeDup[e+h,e-h:l])[]
?l=f l[0]

Try it online!

Defines the function ? :: [Int] -> Int using f :: [Int] -> ([Int] -> Int) as a helper to reduce over each possible sum after an addition or subtraction.

Answer 25

Java 8, 207 83 44 bytes

s->Long.bitCount(s.reduce(1L,(r,c)->r|r<<c))

Port of @xnor's Python 2 answer.
-39 bytes thanks to @Jakob.

Try it online.

s->               // Method with Long-Stream parameter and long return-type
  Long.bitCount(  //  Return the amount of 1s in the binary representation of:
    s.reduce(1L,  //   Result-Long, starting at 1
     (r,c)->      //   Loop pair-wise (result,current):
      r|          //    Bitwise-OR the result `r` with:
        r<<c))    //    result `r` bitwise left-shifted by the current `c`

Answer 26

APL (Dyalog Classic), 21 bytes

⍴∘∪⊢+.×1-2×2(⍴⍨⊤∘⍳*)⍴

Try it online!

Explanation

2(⍴⍨⊤∘⍳*)⍴

A function train equivalent to {((⍴⍵)⍴2)⊤⍳(⍴⍵)}, which generates a matrix that has the binary representations of 0 to the length of the input as columns

1-2×

Maps 1s to -1s and 0s to 1s

⊢+.×

Matrix multiplication with the input, which gives an array of all possible sums

⍴∘∪

Remove duplicates, then count

Answer 27

Java 8, 85 bytes

Another Java port of xnor's answer. Like the original answer, this uses an arbitrary-precision bitmap so that there's no upper limit on the size of a subset sum.

It's a lambda from a sequential java.util.stream.Stream<Integer> to int.

s->s.reduce(java.math.BigInteger.ONE,(a,e)->a.or(a.shiftLeft(e)),(u,v)->u).bitCount()

Try It Online

Note that the combiner (the third argument to reduce) is unused since the stream is sequential. The function I chose is arbitrary.

Answer 28

Julia 0.6, 54 52 bytes

V->(~W=W==[]?0:∪([n=W[] -n].+~W[2:end]))(V)|>endof

Try it online!

(-2 bytes by replacing ¬ with ~, thanks to Jo King)

Works for all test cases. Makes use of broadcast to collect all possible sums, then counts them.

Explanation:

function g_(V)
  function inner(W)  #named ~ in golf version to save bytes
    W == [] ? 0 :    #return 0 when input empty (base case)
    ∪(               #unique elements of
      [n=W[] -n]     #take the first element and its negation
      .+             #broadcast-add that to each element of
      inner([2:end]) #sign-swapping sums of the rest of the array
     )
  end                #returns the list of unique elements out of those sums
  return endof(inner(V)) #return the length of that list
end

---

Older solution:

Julia 0.6, 64 bytes

N->endof(∪([2(i&2^~-j>0)-1 for i=0:~-2^(l=endof(N)),j=1:l]*N))

Try it online!

Works for input arrays with length upto 63 (so doesn't work for the last test case, which is fine according to OP).

Explanation:

function f_(N)
  endof(                            #length of
        ∪(                          #unique elements of
          [
           (i & 2^(j-1) > 0)        #check j'th bit (from right) of i
           * 2 - 1                  #convert bit value from (0,1)=>(-1,1)
           for i = 0:2^endof(N)-1,  #where i is numbers 0 to 2^length(N)-1
           j = 1:endof(N)           #and j is 1 to length(N) (i.e. the bits in i)
          ]                         #so we have a matrix [-1 -1 -1;1 -1 -1;1 -1 1;...]
          *                         #matrix multiply that with the input array, 
          N                         #thus calculating different combinations of 
         ))                         #sign-swapping sums
end

Answer 29

JavaScript (Babel Node), 64 bytes

F=([f,...r],s=[0])=>f?F(r,s.flatMap(x=>[x+f,x])):new Set(s).size

Try it online!

This won't work for last testcase.

---

More effective solution (works on last testcase):

JavaScript (Babel Node), 71 bytes

F=([f,...r],s=[0])=>f?F(r,[...new Set(s.flatMap(x=>[x+f,x]))]):s.length

Try it online!

---

This won't work in a real browser due to Array#smoosh.

Thanks to Bubbler, [x+f,x-f] -> [x+f,x] saves 2 bytes.

Answer 30

Red, 73 bytes

func[b][s:[0]foreach n b[foreach m s[s: union s reduce[m + n]]]length? s]

Port of Dennis' Python 2 answer. Does not handle the last test case.

Try it online!

Answer 31

Japt, 9 bytes

Saved 1 byte thanks to @Shaggy

à mx â ÊÄ

Try it online! This is a slightly modified port of Dennis' Jelly answer, credits to him for the idea. Explanation:

à             Take all non-empty subsets of the input array 
  mx           and sum them
     â Ê      Return the amount of unique sums
        Ä      plus one (to account for the non-empty subset)

Answer 32

Stax, 12 bytes

Çσ▓╥7Cφ1╝╥ò1

Run and debug it

Doesn't handle the last test case in acceptable time.

Explanation (unpacked):

0]s{cN\{+K$uF% Full program, implicit input
0]s            Put [0] under input (array of sums)
   {        F  Foreach:
    cN\          x -> [x, -x]
       { K       Cartesian join:
        +          Add
          $u     Flatten and unique
             % Length
               Implicit output

Answer 33

C (gcc), 236 208 204 bytes

• Saved twenty-eight thirty-two bytes thanks to ceilingcat.

*s,i,g,n;S(w,a,p,_)int*p,*w;{if(_-a)for(_[p]=2;_[p]--;)S(w,a,p,-~_);else{for(*s=0,i=a;i--;)*s+=~(p[i]*2)*w[i];s++;}}f(w,a)int*w;{int p[a+1],r[g=1<<a];s=r;for(S(w,a,p,n=0);g--;wmemchr(r,r[g],g)||++n);w=n;}

Try it online!

Answer 34

Retina, 27 bytes

+`\d+ ?
*@$%"$&*
%O`.
D`
.+

Try it online!

Explanation

+`\d+ ?
*@$%"$&*

For each number, remove the space after it if there is one,. Then split the line into two, one with the number replaced with that many @s, and another with the number replaced with that many _s. Loop until no more numbers exist. That generates all combination, albeit with some duplicates.

%O`.

For each line, sort the characters. With this, there is a 1-1 correspondence between a sum and this "@_" representation.

D`

Deduplicate the lines.

.+

Count the non-empty lines.