# Infer pluses and minuses

### The problem

Consider an equation such as      "3 ± 2 ± 4 ± 1 = 4"      and determine if there exists a sequence of pluses and minuses that makes it arithmetically correct. If it exists, exhibit it. For instance, [-, +, -] works in this case:      "3 - 2 + 4 - 1 = 4".

• Sometimes it's impossible: e.g.      "3 ± 5 = 7"      has no solution. Your code needs to determine this.

• Other times, multiple solutions are possible: for      "1 ± 2 ± 4 ± 3 ± 1 = 1"      , both [-, +, -, +] and [+, -, +, -] are valid. Your code only needs to exhibit one but may also exhibit all.

### The challenge

Code golf: write the shortest function or program that solves the problem.

Assumptions

• All numbers (both left and right of the equal sign) are non-negative integers. There may be zeroes.

• There is just one number to the right of the equal sign.

• There is no ± at the left of the first number.

(2 ± 3 = 1 has no solution)

• Partial sums may be negative (but the total sum will be non-negative).

• There are at least 3 numbers in the input (i.e. at least 2 on the left hand side, plus the result).

I/O

• You will take a sequence of N numbers ([a1, a2, ...aN-1, aN]), where a1, a2, ...aN-1 are addends and aN is the result.

Alternatively, you may choose to get aN separately from the rest.

• You are free to choose what is a "sequence" (a list, or an array, or literals via stdin separated by space or newline or comma, or ...).

• If there is a solution, you should output a sequence of N-2 "plus"-signifying and "minus"-signifying constants, which may be represented as you prefer (("+", "-"), or (+1, -1,), or (+1, 0), or (NaN, 4), or ...).

There are N-2 symbols total. You must not output the (implicit) "plus" to the left of the first addend.

• If there is no solution, you should have a predictable behaviour that signifies "no solution". This can be returning/printing a specific constant or throwing an exception or terminating without output.

Having a program that predictably doesn't terminate is also acceptable.

### Examples

• 3 2 4 1 4- + -
• 3 5 7none
• 1 2 4 3 1 1+ - + - or - + - + or both
• 2 3 1none
• 11 3 0 8- + or - - or both
• 0 15 15+
• 4 9 6 1- +
• 8 2 3 3- -
• 8 4 5 1 16+ + -
• This is what I thought the challenge codegolf.stackexchange.com/questions/272800/… was, from reading only its title. So I went ahead and asked it. Commented Apr 26 at 15:27
• The input should not give you aN separately from the rest. Why this strict input format? Commented Apr 26 at 15:29
• @Arnauld I thought there could be clever ways of getting "organically" to the evaluation of the last number using the logic designed for the problem, without using boilerplate to split the sequence upfront, and these clever ways could be rewarded. But I'm not too sure. So I removed the constraint. Commented Apr 26 at 15:46
• If there are multiple solutions may we output all? Commented Apr 26 at 16:02
• @DomHastings you can if you want. But one is enough. Just don't intertwine them: output them sequentially (optionally separated). Commented Apr 26 at 16:06

# K (ngn/k), 14 bytes

-1 thanks to naffetS

&~*{x-/:y,-y}/


Attempt This Online!

Return a 2d list with solutions in reverse order. -+ are denoted by 01.

   {x-/:y,-y}/  all values obtainable by inserting -/+
*             enforce last op is -
&~              locate 0s

• Whoa, that's short. How does it work? Commented Apr 26 at 20:03
• Can the outputs be in reverse order?
– Tbw
Commented Apr 28 at 0:41
• @Tbw considering whether or not it's reversed isn't particularly important for the problem, I don't see why not (and it's a trivial change if not, anyways)
– att
Commented Apr 28 at 1:19
• x-/:y,-y -1 byte Commented Apr 28 at 21:07

# Perl 5 + -a -M5.10.0, 43 bytes

Outputs all valid solutions. Outputs nothing if there's no solution.

# Python 3,  75  67  64 bytes

-8 bytes thanks to Jitse (by placing the output in r - a very smart golf!).

f=lambda a,b,*r:f(a+b,*r,-2)or f(a-b,*r,-3)if-1<r[0]else(a==b)*r


A recursive function that accepts the full sequence of non-negative integers as arguments in order $$\a_1, a_2, \cdots, a_N\$$ and returns a tuple of instructions as integers, where -2 means add and -3 means subtract, representing one way that works, or an empty tuple if not possible.

Try it online!

### How?

The first two terms of the sequence are a and b, the rest of the sequence is r.
If r's first element is greater than -1 the function is called with the first two terms added and -2 "instruction" is appended to r but if that results in an empty tuple then the function is called with the second term subtracted from the first along an additional -3 "instruction".
However, if r's first element is -2 or -3 then r is returned if a==b otherwise an empty tuple is returned.

• Can be f=lambda a,b,*r:f(a+b,*r,'+')or f(a-b,*r,'-')if 0==0*r[0]else(a==b)*r since the input always contains at least 3 numbers Commented Apr 29 at 11:28
• Nice stuff @Jitse, thanks! Have golfed another few bytes by moving to negative integers. Commented Apr 29 at 15:31

# J, 26 24 bytes

(##:@i.@#)@(=]F..(+,-~))


Attempt This Online!

Outputs all solutions or an empty list when none exists. 1 = -, 0 = + .

• ]F..(+,-~) Fold forward +/-, catting both options to the accumulated result each time
• = Where does that equal the left input? Returns boolean list.
• # Use that 0-1 list to filter...
• #:@i.@# The numbers 0 1 2 ... <len of list - 1> converted to binary

Worth noting this is a similar idea to att's nicer K solution... what makes that more elegant is K's ability to "find" 1s in a multidimensional list, return a lookup path directly to that list as a list of indexes for each axis. This can also be thought of as the result of a binary search algorithm.

J's I., on the other hand, only works for 1 dimensional lists, so we have to deal with some boring mechanics manually to accomplish the same thing.

# R, 85 82 bytes

\(a,s=expand.grid(rep(list(c(-1,1)),sum(a|1)-2)))s[apply(s,1,\(x)!c(1,x,-1)%*%a),]


Attempt This Online!

Takes input as a vector $$\[a_1, a_2, \ldots, a_{N-1}, a_N]\$$ and returns a matrix of ±1s with solutions in rows. For "none", the function outputs numeric(0).

# R, 55 bytes

Takes $$\a_N\$$ as a separate argument, returns a matrix of all solutions with 1/2 for -/+.

\(a,b)which(Reduce(\(x,y)x%o%c(1/y,y),2^a)==2^b,T)[,-1]


Attempt This Online!

The size of numbers this can handle is fairly limited by the powers of 2 a double value can represents.

# JavaScript (ES6), 66 bytes

Returns either a binary string (with 0 for - / 1 for +) or undefined if there's no solution.

f=([n,...a],s=0,o)=>a+a?f(a,s+n,o?o+1:[])||o&&f(a,s-n,o+0):s==n&&o


Try it online!

### Commented

f = (          // f is a recursive function taking:
[ n,         //   n = next value from input array
...a ], //   a[] = remaining values
s = 0,       //   s = sum
o            //   o = output (initially undefined)
) =>           //
a + a ?        // if a[] is not empty:
f(           //   do a 1st recursive call:
a,         //     pass a[]
s + n,     //     add n to s
o ?        //     if o is defined:
o + 1    //       append '1' for '+' to o
:          //     else:
[]       //       initialize o to [] (coerced to
//       an empty string, but truthy)
) ||         //   end of recursive call
o &&         //   if o is defined,
f(           //   do a 2nd recursive call:
a,         //     pass a[]
s - n,     //     subtract n from s
o + 0      //     append '0' for '-' to o
)            //   end of recursive call
:              // else:
s == n && o  //   if s = n, return o


# Uiua 0.11.0, 2712 bytes SBCS

≡⇌⊚=/(⊟⊃-+:)


Similar to @att's K answer, so upvote that one too. Takes the list and $$\a_N\$$ on stack and returns all possible +/- choices as an array of 1s and 0s, with an empty list if not possible.

## Explanation

≡⇌⊚=/(⊟⊃-+:)
/(     ) # fold the list by
⊃-+:  # a-b and a+b
⊟      # combine as two rows of a new array
=         # test equal to a_N element-wise
⊚          # get coordinates of 1s
≡⇌           # reverse each row


## Old solution

⊡⊗:/+⍉⊙:⊃×∘¬×2☇1⇡×2⊃±¤⊙-:°⊂


## Explanation

°⊂  # take first element off of list
:   # swap the top two of stack
⊙-  # subtract a1 from aN
⊃±¤ # get the signs of the list (all 1s)
# and a copy with an axis added
⇡×2 # *2 (all 2s) and range: all binary lists
☇1  # make it rank 2
¬×2 # not(x*2), changes 0,1 to 1,-1
⊃×∘ # multiply by list, keeping 1,-1 array
⊙:  # flip positions 2 and 3 on stack
/+⍉ # sum each row
⊗:  # find the index of the first aN-a1
⊡   # pick that from the 1,-1 array, error if no solution


# Python, 105 91 bytes

- 14 bytes thanks to xnor

def f(l,n,o=[]):
if[n]==l:print(o)
if l[1:]:c,d,*r=l;[f([c+a*d]+r,n,o+[a])for a in[1,-1]]


I have very little experience of golfing in Python, so any tips would be appreciated.

Attempt This Online!

• Some tips: You can save a space after an if by flipping if[n]==len(l). Instead of conditionally returning to quit, you can negate the condition and only do the last two lines if it's true. Those lines can be semicolon separated, and on the same line after the if.
– xnor
Commented Apr 28 at 14:52
• @xnor thanks a lot! Commented Apr 28 at 15:19

# Vyxal, 78 bitsv2, 9.75 bytes

L‹k+↔'1p¹*∑⁰=


Try it Online!

Bitstring:

011000010011100110100110111001010111110001011011110111001100010101101101001001


A silly little answer that might be golfable with a better algorithm. Outputs all possible solutions, or an empty list for no solutions. Represents - as -1 and + as 1.

## Explained

L‹k+↔'1p¹*∑⁰=­⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁢⁢⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏‏​⁡⁠⁡‌⁢⁡​‎‎⁪⁡⁪⁠⁪⁣⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁢⁪‏‏​⁡⁠⁡‌⁢⁢​‎‎⁪⁡⁪⁠⁪⁣⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁤⁡⁪‏‏​⁡⁠⁡‌⁢⁣​‎‎⁪⁡⁪⁠⁪⁣⁤⁪‏‏​⁡⁠⁡‌­
L‹  ↔          # ‎⁡Combinations with replacement of length (a0...a(n-1) length - 1) of
k+           # ‎⁢the list [1, -1]
'         # ‎⁣Filtered to keep combinations where:
1p       # ‎⁤  Prepending 1
¹*     # ‎⁢⁡  and transferring the signs of the combination to a0...a(n-1)
∑ =  # ‎⁢⁢  sums to
⁰   # ‎⁢⁣  a(n)
💎


Created with the help of Luminespire.

# Charcoal, 32 bytes

ＩＥΦＥ…Ｘ²⁻Ｌθ²Ｘ²⊖Ｌθ⊖⊗↨⊗ι²¬Σ×ιθ✂ι¹±¹


Attempt This Online! Link is to verbose version of code. Outputs a list of 1s and -1s for the signs with each solution double-spaced. Explanation:

      ²                             Literal integer 2
Ｘ                              Raised to power
θ                          Input list
Ｌ                           Length
⁻                            Subtract
²                         Literal integer 2
…                               Range to
²                       Literal integer 2
Ｘ                        Raised to power
θ                    Input list
Ｌ                     Length
⊖                      Decremented
Ｅ                                Map over values
ι               Current value
⊗                Doubled
↨                 Converted to base
²              Literal integer 2
⊗                  Vectorised doubled
⊖                   Vectorised decremented
Φ                                 Filtered where
ι          Current list
Σ×           Dot product with
θ         Input list
¬             Is zero
Ｅ                                  Map over solutions
✂ι¹±¹    Slice off leading and trailing signs
Ｉ                                   Cast to string
Implicitly print


# Python, 215 209 bytes

-6 bytes by using another input format.

lambda*n,p,r=range,t=len:(x:=[bin(i)[2:].rjust(t(n)-1,'0').replace('1','-').replace('0','+')for i in r(2**~-t(n))],[x[j]for j in r(t(x))if eval(n[0]+"".join([x[j][l]+n[1:][l]for l in r(t(n)-1)])+"==%s"%p)])[1]


The first part of the lambda creates a list with the signs, and the second part evaluates them. Returns [] if there is no solution. Takes input as parameters of stringified ints, followed by a keyword argument taking the RHS value.

=let(d,tocol(A:A,1),ø,tocol(,1),regexreplace(reduce(d,index(mod(sequence(6^5),rows(d)-1)+2),lambda(a,i,if(a=a&"",a,let(r,{chooserows(a,sequence(i-1));index(a,i)*(2*(rand()<0.5)-1);iferror(chooserows(a,sequence(rows(a)-i,1,i+1)),ø)},if(sum(r)=B1,join("+",r),r))))),"\+-","-"))


Put operands in column A, the expected result in cell B1 and the formula in cell B2.

Gives the solution as in 3-2+4-1, or an error when a solution was not found. Works probabilistically up to 7776 rounds which seems plenty with up to 100 small operands or several dozen operands of any size.

Ungolfed:

=regexreplace(
reduce(tocol(A1:A, 1), index(mod(sequence(6^5), rows(tocol(A1:A, 1)) - 1) + 2), lambda(a, i,
if(istext(a), a, let(
null, tocol(æ, 2),
try, index(a, i) * (2 * (rand() < 0.5) - 1),
tail, iferror(chooserows(a, sequence(rows(a) - i, 1, i + 1)), null),
if(sum(result) = B1, join("+", result), result)
)
))),
"\+-", "-"
)


# Jelly, 7 bytes

_,+ɗ/œẹ


A dyadic Link that accepts a list of non-negative* integers*, the summands $$\[a_1, a_2, \cdots, a_{N-1}]\$$, on the left and a non-negative* integer*, the goal $$\a_N\$$, on the right and yields a list of reversed lists of instructions. 1 means subtract while 2 means add.

Try it online! Or see the test-suite.

* Not a necessary restriction, any numbers will do.

### How?

_,+ɗ/œẹ - Link: list of numbers, Summands; number, Goal
/   - reduce {Summands} by:
_       -     {L} subtract {R} (vectorises) -> L-R
+     -     {L} add {R} (vectorises) -> L+R
,      -     {L-R} pair {L+R} -> [L-R, L+R]
œẹ - all multidimensional indices of {Goal}


# Brachylog, 15 bytes

{+.∧1w₄|-.∧w₄}ˡ


Try it online!

Outputs + as 1 and - as 0. Empty output for impossible test cases.

The first n-1 numbers are given as an input list, and the expected result is given as the output variable.

### Explanation

{             }ˡ    Left fold on the input list:
Either…
+.                     Add the 2 numbers together
∧1w₄                 And delayed write a 1 to stdout
|              Or…
-.              Subtract the 2 numbers together
∧w₄           And delayed write an unknown variable (defaults to 0) to stdout
The output of the left fold must match the given output


This predicate will try different combinations of + and - in a left fold over the input list until the result is equal to the expected result given as output.

Once this predicate succeeds, the delayed writes w₄ will be printed out to stdout. If we were to use normal write commands, then it would write everytime it tries a choice, instead of writing the final correct choices.

If the test case is impossible, the predicate will eventually fail after trying everything, and the delayed writes will not be called. Nothing is thus printed to stdout.

f(x:w:y)=[q|q<-mapM(\_->[-1,1])y,sum(zipWith(*)q\$w:y)==last y-x]


Try it online!

# T-SQL, 3378 bytes

I saw this a few days ago, and was thinking of languages I could use to solve this problem. Ended up deciding to write the entire thing in a query on data.stackexchange.com because I had a lot of free time today and was willing to hardcode each and every one of the cases.

This runs in ~3ms on my Chromebook so I think it is as optimized runtime-wise as it gets.

Also note that loops don't exactly work in T-SQL, so I ended up having to brute-force all 33 cases (32 different ways to arrange +/- and the case where nothing works).

Although it is cool that it actually rounds down if one of the inputs is a decimal, I was afraid that might not happen.

DECLARE @a INT
DECLARE @b INT
DECLARE @c INT
DECLARE @d INT
DECLARE @e INT
DECLARE @f INT
DECLARE @g INT
SET @a = ##a##
SET @b = ##b##
SET @c = ##c##
SET @d = ##d##
SET @e = ##e##
SET @f = ##f##
SET @g = ##g##
IF @a + @b + @c + @d + @e + @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'+',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a + @b + @c + @d + @e - @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'+',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a + @b + @c + @d - @e + @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'+',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a + @b + @c + @d - @e - @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'+',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a + @b + @c - @d + @e + @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'-',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a + @b + @c - @d + @e - @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'-',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a + @b + @c - @d - @e + @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'-',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a + @b + @c - @d - @e - @f = @g
SELECT CONCAT(@a,'+',@b,'+',@c,'-',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a + @b - @c + @d + @e + @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'+',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a + @b - @c + @d + @e - @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'+',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a + @b - @c + @d - @e + @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'+',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a + @b - @c + @d - @e - @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'+',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a + @b - @c - @d + @e + @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'-',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a + @b - @c - @d + @e - @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'-',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a + @b - @c - @d - @e + @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'-',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a + @b - @c - @d - @e - @f = @g
SELECT CONCAT(@a,'+',@b,'-',@c,'-',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a - @b + @c + @d + @e + @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'+',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a - @b + @c + @d + @e - @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'+',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a - @b + @c + @d - @e + @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'+',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a - @b + @c + @d - @e - @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'+',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a - @b + @c - @d + @e + @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'-',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a - @b + @c - @d + @e - @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'-',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a - @b + @c - @d - @e + @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'-',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a - @b + @c - @d - @e - @f = @g
SELECT CONCAT(@a,'-',@b,'+',@c,'-',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a - @b - @c + @d + @e + @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'+',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a - @b - @c + @d + @e - @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'+',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a - @b - @c + @d - @e + @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'+',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a - @b - @c + @d - @e - @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'+',@d,'-',@e,'-',@f,'=',@g)
ELSE IF @a - @b - @c - @d + @e + @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'-',@d,'+',@e,'+',@f,'=',@g)
ELSE IF @a - @b - @c - @d + @e - @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'-',@d,'+',@e,'-',@f,'=',@g)
ELSE IF @a - @b - @c - @d - @e + @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'-',@d,'-',@e,'+',@f,'=',@g)
ELSE IF @a - @b - @c - @d - @e - @f = @g
SELECT CONCAT(@a,'-',@b,'-',@c,'-',@d,'-',@e,'-',@f,'=',@g)
ELSE SELECT 'Error'


Try it online (also commented out version)

# Python, 132 bytes

lambda e,f,*a:{p for p in permutations("+-"*len(a),len(a))if f+eval("".join(x+str(y)for x,y in zip(p,a)))==e}
from itertools import*


Attempt This Online!

# 05AB1E, 14 bytes

®X‚Ig<ãʒ1š¹*OQ


Two separated inputs $$\[a_0,...,a_{n-1}]\$$ and $$\a_n\$$. Output as a list of all possible results, with -1 for - and 1 for +.

Explanation:

®X‚            # Push pair [-1,1]
Ig<         # Push the length-1 of the first input-list
ã        # Take the cartesian product of the two
ʒ       # Filter this list:
1š     #  Prepend a 1
¹*   #  Multiply the values at the same positions to the first input-list
O  #  Sum them together
Q #  Check whether it equals the (implicit) second input-integer
# (after which the filtered list is output implicitly)