找到一个范围内的子集

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