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

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 8

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 9

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 10

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

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 14

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 15

APL (Dyalog Classic), 12 11 bytes

-1 thanks to H.PWiz

≢⊃(+∪⊢)/⎕,0

Try it online!

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

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 22

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

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 26

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

Desmos, 90 74 bytes

-16 bytes thanks to Aiden Chow!

f(A)=unique(∑_{j=1}^a(-1)^{floor([0...2^a]2/2^j)}A[j]).length
a=A.length

Try it on Desmos!

Brute-forces all possible sums; then counts the number of distinct sums.

The exact choice of + or - is encoded in the binary digits of i, ignoring the zeroth bit because Desmos arrays are 1-indexed.

Answer 30

Nekomata + -n, 3 bytes

ŋ∑ũ

Attempt This Online!

ŋ∑ũ
ŋ       Non-deterministically negate some elements of the input
 ∑      Sum
  ũ     Unique values

-n counts the number of possible outputs.