# Sign-Swapping Sums

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 , so the shortest valid solution (measured in bytes) wins.

• Do we have to handle the case where the input is the empty array? Commented May 10, 2018 at 2:10
• @ChasBrown the input is non-empty, according to the post. Commented May 10, 2018 at 2:18
• @EriktheOutgolfer It's effectively saying if your array is all identical numbers (e.g. [2,2,2,2,...] ) the answer should be the length of the array + 1. This is because in this case the position of the signs is irrelevant and only the number of each matter Commented May 10, 2018 at 13:58
• @EriktheOutgolfer It's wasn't intended as a joke; it's an infinite number of test cases! Commented May 10, 2018 at 14:17
• With the exception of the [s]*n family, all test cases can be computed as sum of elements plus one. I suggest adding test cases that fail for this formula (e.g., [2, 4, 8] and [1, 2, 27]). Commented May 10, 2018 at 17:48

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

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


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

• Nice explanation! Commented May 10, 2018 at 12:32

# Python 2, 55 bytes

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


Try it online!

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

• Could you explain how this works? Did you come up with it yourself, or is it some known result? Commented Jul 2, 2018 at 18:55
• @sundar It's not that complicated. This answer calculates the unique sums (not sign-swapping) like many other answers. Each bit in k corresponds to a sum. k<<n adds n to each sum. Oring with k stores these new sums in k whilst keeping all the previous ones, and duplicated Sims are not recorded Commented Jul 5, 2018 at 14:33
• Ah, the trail of breacrumbs leads back to JungHwan Min's bijection idea, that was the main insight I was missing. Here each subset sum is represented by a 1 in that position in the bitstring (with the initial 1 in the LSB representing the sum 0 for the empty subset). Still not something I'd call "not that complicated", but that may just be my inexperience speaking. :) Commented Jul 6, 2018 at 15:39

# 05AB1E, 4 bytes

æOÙg


Utilizes the same approach used in Dennis’ Jelly answer.

Try it online!

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.

• Nice answer! I hoped something like f x=sum[1|i<-[0..sum x],elem i$sum<$>mapM(:[0])x] would be shorter than the import, but apparently, it isn't.
– lynn
Commented May 10, 2018 at 13:02
• Nice, even shorter than the translation of the Mathematica one, although I think it’s prettier: import Data.List;length.foldr((<*>)union.map.(+))[0] Commented May 11, 2018 at 0:44

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

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
}

• Save some bytes with t: TIO Commented May 10, 2018 at 12:59
• and sum(v|1) is a byte shorter than length(v) Commented May 10, 2018 at 13:46

# Octave / MATLAB, 4541 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!

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

• That's a cool way to do it! Commented May 10, 2018 at 6:03

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

# Pyth, 5 bytes

l{sMy


Utilizes the same approach used in Dennis’ Jelly answer.

Try it here.

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

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

# APL (Dyalog Classic), 12 11 bytes

-1 thanks to H.PWiz

≢⊃(+∪⊢)/⎕,0


Try it online!

• As has been noted in other answers, -⍨ can be ⊢ Commented May 11, 2018 at 0:19
• @H.PWiz thanks, very nice!
– ngn
Commented May 11, 2018 at 0:34

# Perl 5-p, 39 bytes

s/^| /{+,-}/g;$_=grep!$s{eval$_}++,glob  Try it online! # 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! # 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  • Equivalent to the Pyth answer, essentially character for character. Commented May 10, 2018 at 18:24 # Perl 6, 33 bytes {+set ([X](^2 xx$_)XZ*$_,)>>.sum}  Try it online! # 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  # 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.

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

# APL (Dyalog Classic), 3433 32 bytes

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


Try it online!

Thanks to @ngn for -1 byte!

• 1-⍨≢⍵ -> ≢1↓⍵
– ngn
Commented May 10, 2018 at 11:36
• +.×⍨ -> +.×
– ngn
Commented May 10, 2018 at 11:59
• The latter one doesn't work, I'm afraid. Commented May 10, 2018 at 13:47
• oops, I don't know why I thought you're applying +.× on vectors... sorry
– ngn
Commented May 10, 2018 at 14:10

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

• Here's a golfed version of the reference solution in Haskell; not sure how much it can carry over to Clean but you might be able to get something out of it. Commented May 14, 2018 at 17:16
• @EsolangingFruit Thanks, but it's already using the same approach and I can't find a way to shorten it even with the reference solution golfed. Commented May 14, 2018 at 21:43

# 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

# Java 8, 20783 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.

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

• 44 bytes is all we need! Taking a stream of Long: s->Long.bitCount(s.reduce(1l,(a,e)->a|a<<e)). Commented Jun 22, 2018 at 5:48
• @Jakob Thanks! I always forget about .reduce (and .bitCount as well I might add.. >.>) -39 bytes right there! :) Commented Jun 22, 2018 at 6:50
• Also I just made an arbitrary-precision version. Looks like the cheapest way to do it is still with a bitmap rather than sets. Commented Jun 22, 2018 at 15:12

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

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


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

• 74 bytes Commented Aug 17, 2023 at 5: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.