24
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Do we have to handle the case where the input is the empty array? \$\endgroup\$ – Chas Brown May 10 '18 at 2:10
  • \$\begingroup\$ @ChasBrown the input is non-empty, according to the post. \$\endgroup\$ – JungHwan Min May 10 '18 at 2:18
  • \$\begingroup\$ Hm, I can't understand how the third test case works, care to explain please? \$\endgroup\$ – Erik the Outgolfer May 10 '18 at 12:53
  • \$\begingroup\$ @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 \$\endgroup\$ – reffu May 10 '18 at 13:58
  • \$\begingroup\$ @reffu It's more of a joke, it does look kinda like it has been included there by error. \$\endgroup\$ – Erik the Outgolfer May 10 '18 at 14:09

34 Answers 34

13
\$\begingroup\$

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.

\$\endgroup\$
8
\$\begingroup\$

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

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice explanation! \$\endgroup\$ – Luis Mendo May 10 '18 at 12:32
6
\$\begingroup\$

Python 2, 55 bytes

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

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Could you explain how this works? Did you come up with it yourself, or is it some known result? \$\endgroup\$ – sundar - Reinstate Monica Jul 2 '18 at 18:55
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – H.PWiz Jul 5 '18 at 14:33
  • \$\begingroup\$ 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. :) \$\endgroup\$ – sundar - Reinstate Monica Jul 6 '18 at 15:39
5
\$\begingroup\$

05AB1E, 4 bytes

æOÙg

Utilizes the same approach used in Dennis’ Jelly answer.

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Lynn May 10 '18 at 13:02
  • \$\begingroup\$ Nice, even shorter than the translation of the Mathematica one, although I think it’s prettier: import Data.List;length.foldr((<*>)union.map.(+))[0] \$\endgroup\$ – Jon Purdy May 11 '18 at 0:44
5
\$\begingroup\$

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
  }
\$\endgroup\$
  • \$\begingroup\$ Save some bytes with t: TIO \$\endgroup\$ – JayCe May 10 '18 at 12:59
  • \$\begingroup\$ and sum(v|1) is a byte shorter than length(v) \$\endgroup\$ – Giuseppe May 10 '18 at 13:46
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ That's a cool way to do it! \$\endgroup\$ – JungHwan Min May 10 '18 at 6:03
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Pyth, 5 bytes

l{sMy

Utilizes the same approach used in Dennis’ Jelly answer.

Try it here.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Classic), 12 11 bytes

-1 thanks to H.PWiz

≢⊃(+∪⊢)/⎕,0

Try it online!

\$\endgroup\$
  • \$\begingroup\$ As has been noted in other answers, -⍨ can be \$\endgroup\$ – H.PWiz May 11 '18 at 0:19
  • \$\begingroup\$ @H.PWiz thanks, very nice! \$\endgroup\$ – ngn May 11 '18 at 0:34
2
\$\begingroup\$

Perl 5 -p, 39 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Equivalent to the Pyth answer, essentially character for character. \$\endgroup\$ – isaacg May 10 '18 at 18:24
2
\$\begingroup\$

Perl 6, 33 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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

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.

\$\endgroup\$
2
\$\begingroup\$

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

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

APL (Dyalog Classic), 34 33 32 bytes

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

Try it online!

Thanks to @ngn for -1 byte!

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

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Esolanging Fruit May 14 '18 at 17:16
  • \$\begingroup\$ @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. \$\endgroup\$ – Οurous May 14 '18 at 21:43
1
\$\begingroup\$

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

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

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

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.

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

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

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.

\$\endgroup\$
  • \$\begingroup\$ You can use [x+f,x] in place of [x+f,x-f] (proof by JungHwan Min). \$\endgroup\$ – Bubbler May 10 '18 at 3:44
  • \$\begingroup\$ +2 bytes for ES6 version: F=([f,...r],s=[0])=>f?F(r,[...s,...s.map(x=>x+f)]):new Set(s).size \$\endgroup\$ – Neil May 10 '18 at 9:25
  • \$\begingroup\$ @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... \$\endgroup\$ – tsh May 10 '18 at 9:49
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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