找到一個範圍內的子集

Question

我怎樣才能找到一個數組的子集，其元素的總和在給定的範圍內？

例如：

let a = [ 1, 1, 3, 6, 7, 50] 
let b = getSubsetSumRange(3, 5) 

所以B可能是[1，1,3]，[1,3]，[3]，[1，3];我只需要其中一個的順序並不重要。

Answer 1

你可能會喜歡用動態規劃的方法來解決這個問題。

讓F[i][j]具有價值true如果有可能從原來的子集a[1..i]所以選擇數字中的一些數字，他們的總和等於j。

i將明顯變化從1到的a長度，並且從j到0包含性max，其中max是從給定的範圍內的第二數目。

F[i][0] = true所有i的定義（您可以隨時選擇空子集）。

然後F[i][j] = F[i - 1][j - a[i]] | F[i - 1][j]

按道理這意味着，如果你能選擇的元素1..i-1與和j一個子集，那麼你顯然可以用集1..i做到這一點，如果你能選擇的元素與和j - a[i]一個子集1..i-1，然後通過將新元素a[i]添加到該子集中，您可以獲得所需的總和j。

你已經計算出的F值後，你可以找到任何F[n][j]是true爲趴在理想範圍值j。

說您發現號碼爲k。然後，找到所需設置的算法將如下所示：

for i = n..1: 
    if F[i - 1][k - a[i]] == True then 
     output a[i] to the answer 
     k -= a[i] 
     if k == 0 
      break