Given a nonempty list of positive integers [X, Y, Z, ...], your job is to determine the number of unique values of ± X ± Y ± Z ...

For example, consider the list [1, 2, 2]. There are eight possible ways to create sums:

  • + 1 + 2 + 25
  • + 1 + 2  - 21
  • + 1  - 2 + 21
  • + 1  - 2  - 2-3
  •  - 1 + 2 + 23
  •  - 1 + 2  - 2-1
  •  - 1  - 2 + 2-1
  •  - 1  - 2  - 2-5

There are six unique sums (5, 1, -3, 3, -1, -5), 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? – Chas Brown May 10 at 2:10
  • @ChasBrown the input is non-empty, according to the post. – JungHwan Min May 10 at 2:18
  • I do realize that the alignment of numbers in the example is actually several pixels off; I tried to adjust everything using hair spaces but they were too wide to get the exact alignment needed. If anybody can find a combination of spaces that makes it perfect, feel free to edit it in. – Esolanging Fruit May 10 at 3:02
  • Hm, I can't understand how the third test case works, care to explain please? – Erik the Outgolfer 2 days ago
  • @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 – reffu 2 days ago

30 Answers 30

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.

Python 2, 55 bytes

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

Try it online!

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.

  • 1
    Nice explanation! – Luis Mendo May 10 at 12:32

05AB1E, 4 bytes

æOÙg

Utilizes the same approach used in Dennis’ Jelly answer.

Try it online!

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.

  • 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 2 days ago
  • Nice, even shorter than the translation of the Mathematica one, although I think it’s prettier: import Data.List;length.foldr((<*>)union.map.(+))[0] – Jon Purdy 2 days ago

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
  }
  • Save some bytes with t: TIO – JayCe 2 days ago
  • and sum(v|1) is a byte shorter than length(v) – Giuseppe 2 days ago

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.

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!

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 ∏(1+xi), where i runs over the elements in the list.

Try it online!

  • That's a cool way to do it! – JungHwan Min May 10 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.

APL (Dyalog Classic), 12 11 bytes

-1 thanks to H.PWiz

≢⊃(+∪⊢)/⎕,0

Try it online!

  • As has been noted in other answers, -⍨ can be – H.PWiz 2 days ago
  • @H.PWiz thanks, very nice! – ngn 2 days ago

Perl 5 -p, 39 bytes

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

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. – isaacg 2 days ago

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

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.

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!

APL (Dyalog Classic), 34 33 32 bytes

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

Try it online!

Thanks to @ngn for -1 byte!

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

Perl 6, 33 bytes

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

Try it online!

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.

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.

  • You can use [x+f,x] in place of [x+f,x-f] (proof by JungHwan Min). – Bubbler May 10 at 3:44
  • +2 bytes for ES6 version: F=([f,...r],s=[0])=>f?F(r,[...s,...s.map(x=>x+f)]):new Set(s).size – Neil May 10 at 9:25
  • @Neil, and... [...s,...s.map(x=>x+f)], s.concat(s.map(x=>x+f)), and, s,s.map(x=>s.push(x+f)) share same length... – tsh May 10 at 9:49

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!

Japt, 10 bytes

à mx â l Ä

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
     â l      Return the amount of unique sums
         Ä     plus one (to account for the non-empty subset)

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
  • 8 bytes Following a similar solution to what Dennis came up with using Jelly – Multi yesterday
  • @Multi Post it yourself, you were probably not even inspired by this one. – wastl yesterday

C (gcc), 236 bytes

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

Try it online!

Java 8, 207 83 bytes

a->{Long k=1L;for(int i:a)k|=k<<i;return k.toString(k,2).replace("0","").length();}

Port of @xnor's Python 2 answer.

Try it online (doesn't work for the last big test case).

a->{            // Method with integer-array parameter and long return-type
  Long k=1L;    //  Long `k`, starting at 1
  for(int i:a)  //  Loop over the input-array
    k|=k<<i;    //   Take `k` left-shifted by `i`, and bitwise-OR it with the current `k`
  return k.toString(k,2)
                //  Take the binary representation of `k`
          .replace("0","").length();}
                //  And return the amount of 1's

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

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.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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