20
\$\begingroup\$

Challenge

The challenge is to write a code that takes a positive integer 'n' as an input and displays all the possible ways in which the numbers from 1 - n can be written, with either positive or negative sign in between, such that their sum is equal to zero. Please remember that you may only use addition or subtraction.

For example, if the input is 3, then there are 2 ways to make the sum 0: 

 1+2-3=0
-1-2+3=0

Note that, the numbers are in order, starting from 1 till n (which is 3 in this case). As it is evident from the example, the sign of the first number can also be negative, so be careful.

Now, 3 was pretty much simple. Let us list all the ways when we consider the number 7. 

 1+2-3+4-5-6+7=0
 1+2-3-4+5+6-7=0
 1-2+3+4-5+6-7=0
 1-2-3-4-5+6+7=0
-1+2+3+4+5-6-7=0
-1+2-3-4+5-6+7=0
-1-2+3+4-5-6+7=0
-1-2+3-4+5+6-7=0

So here, we have got a total of 8 possible ways.

Input And Output

As stated before, the input would be a positive integer. Your output should contain all the possible ways in which the numbers give a sum of zero. In case there is no possible way to do the same, you can output anything you like.

Also, you can print the output in any format you like. But, it should be understandable. For example, you may print it as in the above example. Or, you may just print the signs of the numbers in order. Otherwise, you can also print '0's and '1's in order, where '0' would display negative sign and '1' would display positive sign (or vice versa).

For example, you can represent 1+2-3=0 using: 

1+2-3=0
1+2-3
[1,2,-3]
++-
110
001

However, I would recommend using any of the first three formats for simplicity. You can assume all the inputs to be valid.

Examples

7 ->

 1+2-3+4-5-6+7=0
 1+2-3-4+5+6-7=0
 1-2+3+4-5+6-7=0
 1-2-3-4-5+6+7=0
-1+2+3+4+5-6-7=0
-1+2-3-4+5-6+7=0
-1-2+3+4-5-6+7=0
-1-2+3-4+5+6-7=0

4 ->

 1-2-3+4=0
-1+2+3-4=0

2 -> -

8 ->

 1+2+3+4-5-6-7+8=0
 1+2+3-4+5-6+7-8=0
 1+2-3+4+5+6-7-8=0
 1+2-3-4-5-6+7+8=0
 1-2+3-4-5+6-7+8=0
 1-2-3+4+5-6-7+8=0
 1-2-3+4-5+6+7-8=0
-1+2+3-4+5-6-7+8=0
-1+2+3-4-5+6+7-8=0
-1+2-3+4+5-6+7-8=0
-1-2+3+4+5+6-7-8=0
-1-2+3-4-5-6+7+8=0
-1-2-3+4-5+6-7+8=0
-1-2-3-4+5+6+7-8=0

Scoring

This is , so the shortest code wins!

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ Please note that this is not a dupe of codegolf.stackexchange.com/questions/8655/… , because this challenge is meant to take only n as input and use all the numbers 1-n in order. \$\endgroup\$
    – Manish Kundu
    Commented Feb 3, 2018 at 15:14
  • \$\begingroup\$ May we represent + as N and - as -N, or is that taking it too far? (e.g. 3 -> [[-3,-3,3], [3,3,-3]]) \$\endgroup\$
    – Jonathan Allan
    Commented Feb 3, 2018 at 16:05
  • \$\begingroup\$ @JonathanAllan Isn't that mentioned in the list of output formats? Or did I wrongly interpret your question? \$\endgroup\$
    – Manish Kundu
    Commented Feb 3, 2018 at 16:07
  • \$\begingroup\$ I mean like the 0 and 1 option but using N and -N (see my edit above) \$\endgroup\$
    – Jonathan Allan
    Commented Feb 3, 2018 at 16:09
  • 2
    \$\begingroup\$ @JonathanAllan Yes thats certainly allowed. Make sure you mention that in the answer. \$\endgroup\$
    – Manish Kundu
    Commented Feb 3, 2018 at 16:14

24 Answers 24

Reset to default
8
\$\begingroup\$

Haskell, 42 bytes

f n=[l|l<-mapM(\i->[i,-i])[1..n],0==sum l]

Try it online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 42. \$\endgroup\$
    – DELETE_ME
    Commented Feb 3, 2018 at 15:40
  • 1
    \$\begingroup\$ Shouldn't it be 0== ? \$\endgroup\$
    – Laikoni
    Commented Feb 3, 2018 at 17:48
7
\$\begingroup\$

Jelly, 9 bytes

1,-ṗ×RSÐḟ

Try it online!

Exp

1,-ṗ×RSÐḟ  Main link. Input = n. Assume n=2.
1,-        Literal list [1, -1].
   ṗ       Cartesian power n. Get [[1, 1], [1, -1], [-1, 1], [-1, -1]]
    ×R     Multiply (each list) by Range 1..n.
       Ðḟ  ḟilter out lists with truthy (nonzero)
      S      Sum.

Jelly, 9 bytes

Jonathan Allan's suggestion, output a list of signs.

1,-ṗæ.ÐḟR

Try it online!

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ How about (ab?)using the lax output format with ,Nṗæ.ÐḟR? \$\endgroup\$
    – Jonathan Allan
    Commented Feb 3, 2018 at 15:53
  • \$\begingroup\$ Or alternatively, this output the outputs multiplied by n. \$\endgroup\$
    – DELETE_ME
    Commented Feb 3, 2018 at 15:57
  • \$\begingroup\$ The N and -N output I suggested has been allowed, so that saves one byte :) (just need to mention the format in the answer) \$\endgroup\$
    – Jonathan Allan
    Commented Feb 3, 2018 at 16:34
  • \$\begingroup\$ Not sure how recently it was added, but there's a builtin Ø+ to save a byte over 1,-. \$\endgroup\$
    – Unrelated String
    Commented May 25, 2020 at 19:08
5
\$\begingroup\$

Python 2, 62 bytes

f=lambda n,*l:f(n-1,n,*l)+f(n-1,-n,*l)if n else[l]*(sum(l)==0)

Try it online!

Mr. Xcoder saved 4 bytes with a nifty use of starred arguments.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 62 bytes using *l instead of l=[] \$\endgroup\$
    – Mr. Xcoder
    Commented Feb 3, 2018 at 22:16
4
\$\begingroup\$

Perl, 37 36 bytes

perl -E 'map eval||say,glob join"{+,-}",0..<>' <<< 7
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Nicely done. You can drop -n and <<< if you replace $_ with pop. It doesn't actually improve your score, but it makes the overall expression shorter ;) \$\endgroup\$
    – Chris
    Commented Feb 4, 2018 at 8:08
3
\$\begingroup\$

05AB1E, 11 bytes

®X‚¹ãʒ¹L*O_

Try it online!

The output format for e.g. input 3 is:

[[-1, -1, 1], [1, 1, -1]]

That is, -1-2+3, 1+2-3.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ ¹L can be ā for -1 \$\endgroup\$
    – Kevin Cruijssen
    Commented May 25, 2020 at 15:08
2
\$\begingroup\$

Wolfram Language (Mathematica), 36 bytes

Pick[p={1,-1}~Tuples~#,p.Range@#,0]&

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Husk, 10 bytes

fo¬ΣΠmSe_ḣ

Try it online!

Explanation

Not too complicated.

fo¬ΣΠmSe_ḣ  Implicit input, say n=4
         ḣ  Range: [1,2,3,4]
     m      Map over the range:
      Se     pair element with
        _    its negation.
            Result: [[1,-1],[2,-2],[3,-3],[4,-4]]
    Π       Cartesian product: [[1,2,3,4],[1,2,3,-4],..,[-1,-2,-3,-4]]
f           Keep those
   Σ        whose sum
 o¬         is falsy (equals 0): [[-1,2,3,-4],[1,-2,-3,4]]
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3, 105 bytes

lambda n:[k for k in product(*[(1,-1)]*n)if sum(-~n*s for n,s in enumerate(k))==0]
from itertools import*

Try it online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8),  69 61  58 bytes

Saved 8 bytes thanks to @Neil
Saved 3 bytes thanks to @l4m2

Prints all solutions.

f=(n,o='')=>n?f(n-1,o+'+'+n)&f(n-1,o+-n):eval(o)||print(o)

Try it online!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Do you need k? Something like this: f=(n,o='')=>n?['+','-'].map(c=>f(n-1,c+n+o)):eval(o)||alert(o) \$\endgroup\$
    – Neil
    Commented Feb 3, 2018 at 23:37
  • \$\begingroup\$ @Neil I really don't... Thanks. \$\endgroup\$
    – Arnauld
    Commented Feb 4, 2018 at 0:35
  • 1
    \$\begingroup\$ o+'-'+n => o+-n \$\endgroup\$
    – l4m2
    Commented May 25, 2020 at 13:09
1
\$\begingroup\$

Swift, 116 bytes

func f(n:Int){var r=[[Int]()]
for i in 1...n{r=r.flatMap{[$0+[i],$0+[-i]]}}
print(r.filter{$0.reduce(0){$0+$1}==0})}

Try it online!

Explanation

func f(n:Int){
  var r=[[Int]()]                         // Initialize r with [[]]
                                          // (list with one empty list)
  for i in 1...n{                         // For i from 1 to n:
    r=r.flatMap{[$0+[i],$0+[-i]]}         //   Replace every list in r with the list
  }                                       //   prepended with i and prepended with -i
  print(r.filter{$0.reduce(0){$0+$1}==0}) // Print all lists in r that sums to 0
}
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 2, 91 bytes

lambda x:[s for s in[[~j*[1,-1][i>>j&1]for j in range(x)]for i in range(2**x)]if sum(s)==0]

Try it online!

Returns a list of satisfying lists (e.g., f(3)=[[-1,-2,3], [1,2,-3]])

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog), 38 bytes

{k/⍨0=+/¨k←((,o∘.,⊢)⍣(⍵-1)⊢o←¯1 1)×⊂⍳⍵}

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Pyth, 13 bytes

f!sT.nM*F_BMS

Try it here!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Clean, 79 bytes

import StdEnv
$n=[k\\k<-foldr(\i l=[[p:s]\\s<-l,p<-[~i,i]])[[]][1..n]|sum k==0]

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Retina, 73 bytes

.+
*
_
=_$`
+0`=
-$%"+
(-(_)+|\+(_)+)+
$&=$#2=$#3=
G`(=.+)\1=
=.*

_+
$.&

Try it online! Explanation:

.+
*

Convert the input to unary.

_
=_$`

Convert the number to a list of =-prefixed numbers.

+0`=
-$%"+

Replace each = in turn with both - and +, duplicating the number of lines each time.

(-(_)+|\+(_)+)+
$&=$#2=$#3=

Separately count the number of _s after -s and +s. This sums the negative and positive numbers.

G`(=.+)\1=

Keep only those lines where the -s and +s cancel out.

=.*

Delete the counts.

_+
$.&

Convert to decimal.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 3 + numpy, 104 103 bytes

import itertools as I,numpy as P
lambda N:[r for r in I.product(*[[-1,1]]*N)if sum(P.arange(N)*r+r)==0]

Output is [-1, 1] corresponding to the sign.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ You can remove the space before if for -1 byte \$\endgroup\$
    – ovs
    Commented Feb 3, 2018 at 21:17
1
\$\begingroup\$

C (gcc), 171 161 bytes

k,s;f(S,n,j)int*S;{if(s=j--)S[j]=~0,f(S,n,j),S[j]=1,f(S,n,j);else{for(k=n;k;)s+=k--*S[k];if(!s)for(puts("");k<n;)printf("%d",S[k++]+1);}}F(n){int S[n];f(S,n,n);}

Try it online!

Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

C (gcc), 101 100 83 bytes

Represents addition as 0 and subtraction as 1, but that ultimately that does not matter since for any valid sequence, the complement of the sequence will also result in zero. Returns the permutations by appending them as 32-bit ints to a caller-provided buffer.

i,j,s;f(n,p)int*p;{for(i=1<<n;--i;s||(*p++=i))for(j=s=0;j<n;)s+=i>>j++&1?j:-j;n=p;}

Try it online!

Explanation

i,j,s; // iterators i and j, sum s.
f(n,p)int*p; // declare function
{
  for ( i=1<<n; --i; // iterate over all permutations of n bits (except all-0)
      s||(*p++=i)) // if the permutation summed to 0, append it to the buffer 
   for(j=s=0;j<n;)
     s+= i>>j++&1 // Determine the value of the jth bit
       ?j:-j; // 1=>+(j+1), 0=>-(j+1)
  n=p; // return the pointer to the end of the appended values
}
Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ I do not think you need to use any prettifiers for your output, which could save some bytes. Note that printf("\n") can often be replaced by puts(""). \$\endgroup\$
    – Jonathan Frech
    Commented May 28, 2020 at 23:57
  • \$\begingroup\$ Ah, sorry, I misinterpreted the escape sequences' function. In that case, I think standard I/O also forbids your method since one normally thinks of bytes as a program's output, not its terminal appearance. \$\endgroup\$
    – Jonathan Frech
    Commented May 29, 2020 at 19:03
  • \$\begingroup\$ The general rule for this appears to be codegolf.meta.stackexchange.com/a/5515/46076, which I wasn't aware of until now. I've retracted my flag, since I honestly can't decide whether this answer is valid or not now. See also Default for Code Golf: Input/Output methods Also, fix ping to @JonathanFrech since the previous one didn't go through for me. \$\endgroup\$
    – The Fifth Marshal
    Commented Jun 21, 2020 at 20:01
  • \$\begingroup\$ @pppery I also was not aware of this position, though as it appears to be consensus I guess that is the rule. Thank you for finding the meta post. \$\endgroup\$
    – Jonathan Frech
    Commented Jun 23, 2020 at 5:03
  • \$\begingroup\$ I have updated the function to use a buffer instead of stdout since other submissions return lists, etc. as well. \$\endgroup\$
    – CompilerPotato
    Commented Jun 24, 2020 at 7:55
0
\$\begingroup\$

Perl 6, 43 bytes

{grep *.sum==0,[X] (1..$_ X*1,-1).rotor(2)}

Try it
Returns a sequence of lists

Expanded:

{  # bare block lambda with implicit parameter ｢$_｣

  grep              # only return the ones
    *.sum == 0,     # that sum to zero

    [X]             # reduce with cross meta operator

      (
          1 .. $_   # Range from 1 to the input

        X*          # cross multiplied by

          1, -1

      ).rotor(2)    # take 2 at a time (positive and negative)
}

1..$_ X* 1,-1 ⇒ (1, -1, 2, -2)
(…).rotor(2) ⇒ ((1, -1), (2, -2))
[X] … ⇒ ((1, 2), (1, -2), (-1, 2), (-1, -2))

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

J, 35 30 bytes

-5 bytes thanks to FrownyFrog! 

>:@i.(]#~0=1#.*"1)_1^2#:@i.@^]

Try it online!

Original:

J, 35 bytes

[:(#~0=+/"1)>:@i.*"1(_1^[:#:@i.2^])

How it works

I multiply the list 1..n with all possible lists of coefficients 1 / -1 and find the ones that add up to zero.

                    (             ) - the list of coefficients
                             i.     - list 0 to 
                               2^]  - 2 to the power of the input
                     _1^[:          - -1 to the power of 
                          #:@       - each binary digit of each number in 0..n-1 to 
                 *"1                - each row multiplied by
            >:@i.                   - list 1..n
  (#~      )                        - copy those rows
     0=+/"1                         - that add up to 0
[:                                  - compose

Try it online!

As an alternative I tried an explicit verb, using the approach of cartesian product of +/-:

J, 37 bytes

3 :'(#~0=+/"1)(-y)]\;{(<"1@,.-)1+i.y'

{(<"1@,.-) finds the cartesian products for example:

{(<"1@,.-) 1 2 3
┌───────┬────────┐
│1 2 3  │1 2 _3  │
├───────┼────────┤
│1 _2 3 │1 _2 _3 │
└───────┴────────┘

┌───────┬────────┐
│_1 2 3 │_1 2 _3 │
├───────┼────────┤
│_1 _2 3│_1 _2 _3│
└───────┴────────┘

Too bad that it boxes the result, so I spent some bytes to unbox the values

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ @FrownyFrog Thank you, I was not happy with the right side of my code. \$\endgroup\$
    – Galen Ivanov
    Commented Feb 5, 2018 at 7:08
0
\$\begingroup\$

Not the best but I tried :)

C (Linux GCC)

Entire program: 282 characters

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int n,x,i,s;int main(int c,char**z){n=atoi(z[1]);int a[n];for(x=0;x<n;x++)a[x]=x+1;for(i=0;i<pow(2, n)-1;i++){s=0;for(x=0;x<n;x++){printf("%c%d",i>>x&0x01?'-':'+',a[x]);s+=(i>>x&0x01?-1:1)*a[x];}printf(s!=0?"\r":"=%d \n",s);}}

Just as function: 196 characters

void z(int n){int a[n],x,i,s;for(x=0;x<n;x++)a[x]=x+1;for(i=0;i<pow(2,n)-1;i++){s=0;for(x=0;x<n;x++){printf("%c%d",i>>x&0x01?'-':'+',a[x]);s+=(i>>x&0x01?-1:1)*a[x];}printf(s!=0?"\r":"=%d \n",s);}}

Results

  • n = 4:
+1-2-3+4=0 
-1+2+3-4=0
  • n = 7:
+1-2-3-4-5+6+7=0 
-1+2-3-4+5-6+7=0 
-1-2+3+4-5-6+7=0 
+1+2-3+4-5-6+7=0 
-1-2+3-4+5+6-7=0 
+1+2-3-4+5+6-7=0 
+1-2+3+4-5+6-7=0 
-1+2+3+4+5-6-7=0

Abstract Printing & Just Function: 172 characters

You could shrink the print statements down much more by simply outputting only the +/-'s which are represented by 1/-1 and abstractly representing the entire sum thing, but I still don't think it would beat the other C answers anyway.

That version is:

void z(int n){int a[n],x,i,j,s;for(x=0;x<n;x++)a[x]=x+1;for(i=0;i<pow(2,n)-1;i++){s=0;for(x=0;x<n;x++){j=i>>x&0x01?-1:1;printf("%d ",j);s+=j*a[x];}printf(s!=0?"\r":"\n");}}

Results

  • n = 4:
1 -1 -1 1 
-1 1 1 -1
  • n = 7:
1 -1 -1 -1 -1 1 1 
-1 1 -1 -1 1 -1 1  
-1 -1 1 1 -1 -1 1  
1 1 -1 1 -1 -1 1 
-1 -1 1 -1 1 1 -1 1 
1 1 -1 -1 1 1 -1 
1 -1 1 1 -1 1 -1 1 
-1 1 1 1 1 -1 -1 -1
Improve this answer
\$\endgroup\$
1
0
\$\begingroup\$

T-SQL, 152 bytes

Input is a varchar(max)

Output format is +1+2-3

WITH C as(SELECT @*1d,@+null o,0f
UNION ALL
SELECT~-d,concat(char(44+s),d,o),f+s*d
FROM C,(values(-1),(1))x(s)WHERE d>0)SELECT
o FROM C WHERE f=0and d=0

Try it online

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

R, 82 69 bytes

s=t(expand.grid(rep(list(c(-1,1)),n<-scan())))*1:n;t(s[,!colSums(s)])

Try it online!

Edit: -13 bytes by using built-in expand.grid function to automatically create matrix of all combinations of +1 and -1.

Selects rows of matrix of 1:n in all combinations of positive & negative which sum to zero.

Commented version:

s=t(                    # transpose matrix of:
mapply(rep,             # apply the function 'rep' 
    list(c(-1,1)),      # to the values (-1, 1)
    each=2^(0:(n-1)),   # repeating each by an increasing power-of-2
    length=2^n)         # and making the output length always 2^n
)                       # so: this generates a matrix of all the 
                        # combinations of -1 and 1
                        
t(                      # now transpose the matrix s
s[,                     # taking only the columns with a 
   !colSums(s*1:n)]     # zero sum of multiplying the values
)                       # by the sequence 1:n

Previous (but sadly longer much longer) recursive strategy: 118 bytes

f=function(n,l=NULL,t=0)`if`(n>1,c(f(n-1,c(0,l),t-n),f(n-1,c(1,l),t+n)),`if`(t==n,list(c(0,l)),if(t==-n)list(c(1,l))))

Try it online!

Outputs 1 for + and 0 for - (or the other way around).

Commented version:

f=function(n,l=NULL,t=0){               # n = counts down to 1 recursively
                                        # l = list of signs so far
                                        # t = total so far
    if(n==1){                           # if n is 1...
        if(t-n==0){                     # ...then if t-n makes zero...
            return(list(c("-",l))) }    # add a '-' to the list of signs & return it
        else if(t+n==0){                # ...or, if t+n makes zero...
            return(list(c("+",l))) }    # add a '+' to the list of signs & return it
        else {                          # ...otherwise we can't make zero...
            return(NULL) }              # so return NULL
    } else {                            # if n is greater than 1
        return(c(                       # return the result of calling this function
            f(n-1,c("-",l),t-n),        # using n-1, after applying either a '-'
            f(n-1,c("+",l),t+n)         # or a '+' and updating the total so far
        ))
    }
}
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Vyxal, 9 bytes

k-↔vÞż'∑¬

Try it Online!

Explained

k-↔vÞż'∑¬­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌­
k-↔        # ‎⁡Get all combinations with replacement of the list [-1, 1] with length input
   vÞż     # ‎⁢multiply each item in each list by its one-indexed position
      '    # ‎⁣Filter to keep only lists where:
       ∑   # ‎⁤  The sum
        ¬  # ‎⁢⁡  logically negated is truthy (ie 0)
💎

Created with the help of Luminespire.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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