Manipulate integers to zero

Question

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)

Answer 1

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

Answer 2

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.

Answer 3

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!

Answer 4

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!

Answer 5

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