獲取數組值的組合的總和階

Question

我知道已經有過這幾個類似的問題，但仍有似乎並沒有成爲一個明確的答案，這讓我會問它..

我有一個值爲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 

這是好的，但只有當（構成總和的）值可以從低於那個值的最高值開始限制;在這個例子中5 - 我們可以看到，這個例子和這個數組一起工作。但是如果該數組的限制值是12（getLimitArr(arr, 12)），那麼它將返回11 = 11而不是使用5 + 4 + 3。

我已經這樣做了使用子集但是當陣列超過10我得到內存堆錯誤，因爲它是能夠得到答案之前制定的所有組合。

那麼我們如何通過使用當前格式或利用Scala的函數式編程能力來提高內存效率？

Answer 1

當找到第一個正確的答案時，遞歸通常很有用。

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) 

注意最後一個款項23因爲沒有組合總計爲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 
    } 
}