Make Zero From First 'n' Numbers

15

2

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!

Manish Kundu

Posted 2018-02-03T15:13:03.983

Reputation: 1 947

Please note that this is not a dupe of https://codegolf.stackexchange.com/questions/8655/golf-the-subset-sum-problem , because this challenge is meant to take only n as input and use all the numbers 1-n in order.

– Manish Kundu – 2018-02-03T15:14:00.143

May we represent + as N and - as -N, or is that taking it too far? (e.g. 3 -> [[-3,-3,3], [3,3,-3]]) – Jonathan Allan – 2018-02-03T16:05:50.647

@JonathanAllan Isn't that mentioned in the list of output formats? Or did I wrongly interpret your question? – Manish Kundu – 2018-02-03T16:07:58.723

I mean like the 0 and 1 option but using N and -N (see my edit above) – Jonathan Allan – 2018-02-03T16:09:06.520

2@JonathanAllan Yes thats certainly allowed. Make sure you mention that in the answer. – Manish Kundu – 2018-02-03T16:14:22.273

Answers

7

Haskell, 42 bytes

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

Try it online!

totallyhuman

Posted 2018-02-03T15:13:03.983

Reputation: 15 378

142. – user202729 – 2018-02-03T15:40:54.200

1Shouldn't it be 0== ? – Laikoni – 2018-02-03T17:48:42.783

5

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!

user202729

Posted 2018-02-03T15:13:03.983

Reputation: 14 620

1How about (ab?)using the lax output format with ,Nṗæ.ÐḟR? – Jonathan Allan – 2018-02-03T15:53:01.357

Or alternatively, this output the outputs multiplied by n.

– user202729 – 2018-02-03T15:57:22.517

The N and -N output I suggested has been allowed, so that saves one byte :) (just need to mention the format in the answer) – Jonathan Allan – 2018-02-03T16:34:13.573

5

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.

xnor

Posted 2018-02-03T15:13:03.983

Reputation: 115 687

162 bytes using *l instead of l=[] – Mr. Xcoder – 2018-02-03T22:16:49.300

3

Perl, 37 36 bytes

perl -E 'map eval||say,glob join"{+,-}",0..<>' <<< 7

Ton Hospel

Posted 2018-02-03T15:13:03.983

Reputation: 14 114

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 ;) – Chris – 2018-02-04T08:08:41.973

2

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.

Erik the Outgolfer

Posted 2018-02-03T15:13:03.983

Reputation: 38 134

2

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!

ovs

Posted 2018-02-03T15:13:03.983

Reputation: 21 408

2

Wolfram Language (Mathematica), 36 bytes

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

Try it online!

alephalpha

Posted 2018-02-03T15:13:03.983

Reputation: 23 988

2

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

Zgarb

Posted 2018-02-03T15:13:03.983

Reputation: 39 083

1

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
}

Herman L

Posted 2018-02-03T15:13:03.983

Reputation: 3 611

1

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.

user2699

Posted 2018-02-03T15:13:03.983

Reputation: 538

You can remove the space before if for -1 byte – ovs – 2018-02-03T21:17:23.167

1

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

Chas Brown

Posted 2018-02-03T15:13:03.983

Reputation: 8 959

1

APL (Dyalog), 38 bytes

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

Try it online!

Uriel

Posted 2018-02-03T15:13:03.983

Reputation: 11 708

1

C (gcc), 171 bytes

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

Try it online! Uses 0 for negative and 2 for positive signs.

Jonathan Frech

Posted 2018-02-03T15:13:03.983

Reputation: 6 681

1

Pyth, 13 bytes

f!sT.nM*F_BMS

Try it here!

Mr. Xcoder

Posted 2018-02-03T15:13:03.983

Reputation: 39 774

1

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!

Οurous

Posted 2018-02-03T15:13:03.983

Reputation: 7 916

0

JavaScript (ES6), 69 61 bytes

Saved 8 bytes by getting rid of k, as suggested by @Neil

Prints all solutions with alert().

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

Test cases

Using console.log() instead of alert() for user-friendliness.

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

alert = console.log;

console.log('[7]');f(7)
console.log('[4]');f(4)
console.log('[2]');f(2)
console.log('[8]');f(8)

Arnauld

Posted 2018-02-03T15:13:03.983

Reputation: 111 334

Do you need k? Something like this: f=(n,o='')=>n?['+','-'].map(c=>f(n-1,c+n+o)):eval(o)||alert(o) – Neil – 2018-02-03T23:37:55.620

@Neil I really don't... Thanks. – Arnauld – 2018-02-04T00:35:10.093

0

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!

Galen Ivanov

Posted 2018-02-03T15:13:03.983

Reputation: 13 815

@FrownyFrog Thank you, I was not happy with the right side of my code. – Galen Ivanov – 2018-02-05T07:08:51.713

0

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.

Neil

Posted 2018-02-03T15:13:03.983

Reputation: 95 035

0

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

Brad Gilbert b2gills

Posted 2018-02-03T15:13:03.983

Reputation: 12 713

Asked: 2018-02-03T15:13:03.983

Viewed: 1 235 times

Active: 2018-02-10T11:42:47.830