私はこれにいくつかの同様の質問があったことを知っているが、それでも私はそれを聞いてきます、これに決定的な答えがあるようには思えないScalaの

Question

における配列値の組み合わせの合計を取得します。..

I arrayの値を持ち、合計値がlimitである正しい値を見つけようとしているか、または与えられた組み合わせから（それを超えずに）得ることができる最も近い値を見つけようとしています。

この回答https://stackoverflow.com/questions/23168934/calculating-minimal-subset-with-given-sumを使用して、私はこれがあります。

def getLimitArr(arr: Array[Int], limit: Int): Unit = { 

     scala.util.Sorting.quickSort(arr) // Array(2, 3, 4, 5, 11, 34) 
     var sum = 0L 
     var i = arr.length-1 

     val arr2 = ArrayBuffer[Integer]() 
     while (i >= 0 && sum < limit) { 
     if(sum + arr(i)<=limit) { 
      sum += arr(i) 
      arr2 += arr(i) 
     } 
     i -= 1 // 6, 5, 4, 3, 2, 1 
     } 

    println(arr2.mkString(", ") + " = " + sum) 

    } 

をメインの方法でこれを使用して、それを呼び出す：

val arr = Array(3, 34, 4, 11, 5, 2) 
    getLimitArr(arr, 9) 

返します

println(arr2.mkString(", ") + " = " + sum) // 5, 4 = 9 

これは良いのですが、 （合計を構成する）値が、それよりも低い最高値から作成される場合にのみn限度。この例では5 - この配列で動作します。しかし、この配列の制限値が12（getLimitArr(arr, 12)）の場合、5 + 4 + 3ではなく11 = 11を返します。

私はサブセットを使用して、これを行っているが、配列は、それが答えを得ることができるようになる前に、全ての組み合わせを策定されたとして、私はメモリヒープエラーを取得する10以上であるとき。

私たちはメモリを効率的に使用し、現在のフォーマットを使用したり、Scalaの関数型プログラミング機能を利用したりすることで、どのようにこれを行うでしょうか？

Answer 1

再帰は、最初の正解が見つかると直ちに終了したいときに便利です。 23

def getLimit(nums: Array[Int], limit: Int): Array[Int] = { 
    val subset = nums.filter(limit.>=) 
    if (subset.isEmpty) Array() 
    else (1 to subset.length).flatMap(subset.combinations) 
          .find(_.sum == limit) 
          .fold(getLimit(subset, limit-1))(identity) 
} 

getLimit(Array(3, 34, 4, 11, 5, 2), 5) // res0: Array[Int] = Array(5) 
getLimit(Array(3, 34, 4, 11, 5, 2), 9) // res1: Array[Int] = Array(4, 5) 
getLimit(Array(3, 34, 4, 11, 5, 2), 12) // res2: Array[Int] = Array(3, 4, 5) 
getLimit(Array(3, 34, 4, 11, 5, 2), 24) // res3: Array[Int] = Array(3, 4, 11, 5) 

注最後の和その24

更新

に合計ない組み合わせがないため、より良いショートカットを添加し、この方法は、現在尾再帰的です。

def getLimit(nums: Array[Int], limit: Int): Array[Int] = { 
    val subset = nums.filter(limit.>=) 
    if (subset.sum <= limit) subset 
    else { 
    val res = (1 to subset.length).view 
            .flatMap(subset.combinations) 
            .find(_.sum == limit) 
    if (res.isEmpty) getLimit(subset, limit-1) 
    else res.get 
    } 
}