Compute to 100: Given the digits 123456789, build an expression by inserting "+" or "-" anywhere BETWEEN the digits so that it results to 100. Your answer should return all possible combinations. Example: 1 + 23 - 4 + 5 + 6 + 78 - 9 = 100

Compute100.scala

import scala.collection.mutable.ListBuffer
object Main {

  val digits =  123456789
  val digitsSplit =  digits.toString.map(_.asDigit)
  val sum = 100

  def attachPrefix(prefix:ListBuffer[String], paths:ListBuffer[ListBuffer[String]]) = {
    paths.filter(_.nonEmpty).map(p => prefix ++ p)
  }

  def findPaths(sum:Int, prevNo:Int, index:Int): ListBuffer[ListBuffer[String]] = {
    val prevDigit = Math.abs(prevNo%10)
    if (index >= digitsSplit.length) {
      if(sum == prevNo) ListBuffer(ListBuffer(prevDigit.toString)) else ListBuffer()
    } else {
      val currDigit = digitsSplit(index)
      val attachNo = if(prevNo >= 0) {10*prevNo + currDigit}
      else {10*prevNo - currDigit}

      val plusOptions = findPaths(sum-prevNo, currDigit, index+1)
      val minusOptions = findPaths(sum-prevNo, -currDigit, index+1)
      val joinOptions = findPaths(sum, attachNo, index+1)
      val options = ListBuffer[ListBuffer[String]]()

      options++=attachPrefix(ListBuffer(prevDigit.toString, "+"), plusOptions)
      options++=attachPrefix(ListBuffer(prevDigit.toString, "-"), minusOptions)
      options++=attachPrefix(ListBuffer(prevDigit.toString, "&"), joinOptions)
      options
    }
  }

  def main(args: Array[String]): Unit = {
    findPaths(sum, digitsSplit(0), 1).foreach{s =>
     println(s.mkString("").replace("&", ""))
    }  
  }
}