# Objective

Given a nonempty unordered list of positive integers, decide whether they can be added, negated, or multiplied to yield a single zero. Each given number must be used exactly once.

There is a taboo. Do not multiply zero to anything. Adding zero to anything is OK.

# Examples

## Truthy

List, Solution
[1,1], 1-1
[1,1,2], 2-1-1
[2,3,5], 2+3-5
[2,3,6], 2*3-6
[1,2,3,4], 2-1+3-4
[1,1,3,4], 1*1+3-4
[2,2,3,4], 2*3-2-4
[1,1,2,2,2], (2-1*1)*2-2


## Falsy

[1]
[1,2]
[2,3,4]
[1,3,3,4] ((3-3)*1*4 isn't valid because multiplication by zero is taboo)

• Suggest truthy cases where brackets are unavoidable
– l4m2
Mar 11 at 7:08
• This is essentially 24 game Mar 11 at 14:02
• [1,1,2,2,2] can be solved with 1+1-2+2-2 without parens. A better example might be [1,2,3,9] -> (1+2)*3-9. Mar 12 at 0:56

# JavaScript (ES6), 101 bytes

Returns 0 or 1.

f=a=>a==0|a.some((p,i)=>a.some((q,j)=>i<j&&[p+q,p-q,p*q||f].some(v=>f(q,q[i]=v),q=a.filter(_=>j--))))


Try it online!

### Commented

f = a =>            // a[] = input array
a == 0 |            // success if a[] == [0]
a.some((p, i) =>    // for each value p at index i in a[]:
a.some((q, j) =>  //   for each value q at index j in a[]:
i < j &&        //     abort if i >= j
[               //     otherwise, compute:
p + q,        //       addition
p - q,        //       subtraction
p * q         //       multiplication, whose result is ...
|| f          //       ... invalidated if it's 0
].some(v =>     //     for each value v in the above array:
f(            //       do a recursive call:
q,          //         pass q[]
q[i] = v    //         with q[i] = v
),            //       end of recursive call
q =           //       initialize q[] to ...
a.filter(_ => //       ... a copy of a[] with ...
j--         //         ... the j-th element removed
)             //       end of filter()
)               //     end of some()
)                 //   end of some()
)                   // end of some()

• It fails for [4,6,6,9] 6*6-4*9 (suggested by @l4m2) Mar 11 at 9:27
• @Mukundan314 Thanks for reporting this. Should be fixed. (It was a generic bug, not directly related to this specific test case.) Mar 11 at 9:37
• Neel Shukla: please stop editing this post. Multiplying by 0 is not allowed as per the challenge rules, so 1,2,2,9 is falsy. You can't do (9-1)*(2-2). Mar 11 at 10:29

# Charcoal, 56 bytes

⊞υＡＦυＦＬιＦκ«≔⟦§ιλ§ικ⟧θＦΦ⟦ΠθΣθ↔↨θ±¹⟧∨μν⊞υ⊞ＯΦι∧⁻ξκ⁻ξλμ»¬⌈⌊υ


Try it online! Link is to verbose version of code. Explanation:

⊞υＡＦυ


Start a breadth-first search with the initial list of integers.

ＦＬιＦκ«


Loop over the indices of every pair of integers in the list.

≔⟦§ιλ§ικ⟧θ


Extract the integers.

ＦΦ⟦ΠθΣθ↔↨θ±¹⟧∨μν


Loop over the sum and the absolute difference, and also the product, if it is nonzero.

⊞υ⊞ＯΦι∧⁻ξκ⁻ξλμ


Remove the integers from the list and add the new value, then add the new list to the list of lists to search.

»¬⌈⌊υ


Check whether a zero result was obtained.

# JavaScript (Node.js), 98 bytes

f=(x,a,b)=>[b]<f?x.some((t,i)=>f(x.filter(_=>i--),t,a))|x==a:[a+b,a-b,a*b||f].some(y=>f([...x,y]))


Try it online!

# JavaScript (Node.js), 106 bytes

f=(x,a,b)=>1/b?f([...x,a+b])|f([...x,a-b])|a*b*f([...x,a*b]):x+x?x.some((t,i)=>f(x.filter(_=>i--),t,a)):!a


Try it online!

• Your 96-byte version disagrees with your 106-byte version for e.g. [2,2,2,2,2]. Mar 11 at 11:04
• @Arnauld Should be fix if no stringified number is smaller than "("
– l4m2
Mar 12 at 0:38

# Python3, 292 bytes

lambda v:0 in[*f(v)]
R=range
def f(v):
k=[v]
for i in R(len(v)):
for j in R(i+1,len(v)+1):
if j-1>1 and j-i<len(v):
for t in f(v[i:j]):k+=[v[:i]+[t]+v[j:]]
for i in k:
if len(i)==1:yield i[0];continue
if(V:=i[0]*i[1]):k+=[[V,*i[2:]]]
for I in[-1,1]:k+=[[i[0]+I*i[1],*i[2:]]]


Try it online!

# Scala 3, 387 371 bytes

A port of @Ajax1234's Python answer in scala.

Saved 16 bytes thanks to @ceilingcat

Golfed version (371 bytes). Attempt This Online!

def F(v:List[Int])=f(v).contains(0)
def f(v:List[Int]):LazyList[Int]={val k:LazyList[List[Int]]=LazyList(v)++(for{i<-(0 to v.size-1).to(LazyList);j<-(i+1 to v.size).to(LazyList);if j>2&j-i<v.size;t<-f(v.slice(i,j))}yield v.slice(0,i)++List(t)++v.drop(j));k.flatMap{i=>if(i.size==1)LazyList(i(0))else{LazyList(i(0),i(1),i(0)*i(1))++(i.drop(2):+(i(0)+i(1))):+(i(0)-i(1))}}}


Ungolfed version. Attempt This Online!

object Main {
def main(args: Array[String]): Unit = {
println(F(List(1, 1)))
println(F(List(1, 1, 2)))
println(F(List(2, 3, 5)))
//println(F(List(2, 3, 6)))
println(F(List(1, 2, 3, 4)))
println(F(List(1, 1, 3, 4)))
println(F(List(2, 2, 3, 4)))
println(F(List(1, 1, 2, 2, 2)))
println("-" * 20)
println(F(List(1)))
println(F(List(1, 2)))
println(F(List(2, 3, 4)))
//println(F(List(1, 3, 3, 4)))
//println(F(List(2, 2, 2, 2, 2)))
}

def F(v: List[Int]): Boolean = f(v).contains(0)

def f(v: List[Int]): LazyList[Int] = {
val k: LazyList[List[Int]] = LazyList(v) ++ (for {
i <- (0 until v.length).to(LazyList)
j <- (i + 1 to v.length).to(LazyList)
if j - 1 > 1 && j - i < v.length
t <- f(v.slice(i, j))
} yield v.slice(0, i) ++ List(t) ++ v.drop(j))

k.flatMap { i =>
if (i.length == 1) LazyList(i.head)
else {
val V = i.head * i(1)
LazyList(i.head, i(1), V) ++ (i.drop(2) :+ (i.head + i(1))) :+ (i.head - i(1))
}
}
}
}

• 371 bytes Mar 12 at 4:54