配列を指定し、(+,-,*,/)でNの式を計算します.

私は解法しなければならないのは簡単な暴力の解で、すべての可能性を試して、条件に合った結果を探し出します.より効率的なアルゴリズムがあるはずで、少なくとも枝を切ることができます.暴力的な解だけでは理由がないようで、主にscalaでfunctionalの解法を試み、基礎的なコンポーネント(関数)を構築することで、それらを組み合わせて、最後に結果を得るためだ.
完全なコードは次のとおりです.

object App extends App {

  abstract trait Op {
    def value: Int

    def expression: String

    def isValid: Boolean
  }

  object Op {
    def list(x: Op, y: Op) = List(Add(x, y), Sub(x, y), Mul(x, y), Div(x, y))
  }

  case class Add(left: Op, right: Op) extends Op {
    override def value: Int = left.value + right.value

    override def expression: String = "(" + left.expression + " + " + right.expression + ")"

    override def isValid: Boolean = left.value <= right.value
  }

  case class Sub(left: Op, right: Op) extends Op {
    override def value: Int = left.value - right.value

    override def expression: String = "(" + left.expression + " - " + right.expression + ")"

    override def isValid: Boolean = left.value > right.value
  }

  case class Mul(left: Op, right: Op) extends Op {
    override def value: Int = left.value * right.value

    override def expression: String = left.expression + " * " + right.expression

    override def isValid: Boolean = left.value <= right.value && left.value != 1 && right.value != 1
  }

  case class Div(left: Op, right: Op) extends Op {
    override def value: Int = left.value / right.value

    override def expression: String = left.expression + " / " + right.expression

    override def isValid: Boolean = right.value != 0 && left.value % right.value == 0 && right.value != 1
  }

  case class Val(override val value: Int) extends Op {
    override def expression: String = s"$value"

    override def isValid: Boolean = true
  }

  def splitArray(array: List[Int]): List[(List[Int], List[Int])] =
    array match {
      case Nil => throw new RuntimeException("no empty array allowed here.")
      case x :: y :: Nil => List((List(x), List(y)))
      case h :: tail =>
        (List(h), tail) :: (for {
          (x, y) <- splitArray(tail)
        } yield (h :: x, y))
    }

  def express(nums: List[Int]): List[Op] =
    nums match {
      case Nil => throw new RuntimeException("empty list")
      case x :: Nil => List(Val(x))
      case _ =>
        for {
          (left, right) <- splitArray(nums)
          x <- express(left)
          y <- express(right)
          op <- Op.list(x, y)
          if op.isValid
        } yield op
    }

  def choices(nums: List[Int]): List[List[Int]] = {

    def go(lists: List[List[Int]], i: Int, used: Set[Int]): List[List[Int]] =
      if (i == nums.length) lists
      else {
        for {
          x <- nums
          if (!used(x))
          subChoice <- go(lists ++ lists.map(x :: _), i + 1, used + x)
        } yield {
          subChoice
        }
      }

    go(List(Nil), 0, Set.empty).toSet.toList
  }

  def countDown(nums: Array[Int], res: Int): List[Op] = {
    for {
      list <- choices(nums.toList)
      if (!list.isEmpty)
      op <- express(list)
      if (op.value == res)
    } yield op
  }

  choices(Array(1, 3, 10).toList).foreach(println)

  //  splitArray(Array(1, 3, 7, 10, 25, 50).toList).foreach(println)

  val opList = countDown(Array(1, 3, 7, 10, 25, 50), 765)
  opList.foreach(op => println(op.expression))
}

1.Optraitを使用する理由は、主に2つの役割があります.a.私たちは最後の値だけでなく、765に等しいかどうか、この式自体にも関心を持っています.2.この式が有効かどうかを判断し、計算した結果が整数かどうかを判断する.
2.choices(list)は、choicee(list(1,2)=>[],[1],[2],[1,2],[2],[2,1],[2],[2,1];次に,各組合せでOpを求めることができる.この方法の時間的複雑さはn!,このアルゴリズムは遊びにすぎないことがわかります
3.次に、上記の組み合わせを用いて、式を計算し、a.フィルタリングされた集合を計算する.なぜなら、空のOpを表すために使用されていないからである.b.1つの要素の集合に対して、1つの可能性しかない.その要素自体、Val(x)である.c.複数の要素がある場合、その集合を両側に分割し、Opを再帰的に計算し、Opをマージする必要がある.
Just For Fun.