使用递归组合求和

Question

我是数据结构新手，我正在尝试这个问题组合和

我知道这可能是非常基本的东西，但我正在学习递归，不想了解我做错的地方，以便我可以纠正我的思维过程。

给定一组不同的候选整数和一个目标整数目标，返回候选数字的所有唯一组合的列表，其中所选数字之和达到目标。您可以按任何顺序返回组合。

同一号码可以无限次地从候选人中选择。两个组合是唯一的，如果 频率 至少有一个所选数字不同。

生成的测试用例使得对于给定输入而言，总和达到目标的唯一组合数量少于 150 个组合。

var combinationSum = function(candidates, target) {
    if(candidates.length == 0) return [[]]
    if(target == 0) return [[]]
    if(target<0) return []
    result = []
    for(let i=0; i<candidates.length; i++){
        let arr = [...candidates]
        // take the element
        let result1 = combinationSum([...candidates], target-candidates[i])
        // ignore the element
        result1.forEach((e)=>{e.push(candidates[i])})
        let result2 = combinationSum(arr.slice(0, i).concat(arr.slice(i + 1)), target)
        result.push(...result1, ...result2)
    }
    return result
};

现在，我正在努力寻找组合而不是唯一， 我无法理解为什么这不起作用。

Answer 1

存在三个问题：

• 条件

  candidates.length == 0

  并不能保证您已找到解决方案，因此返回

  [[]]

  还为时过早。您应该首先检查是否达到目标。如果没有，则检查是否没有更多候选者，如果是，那么您没有找到解决方案，应该返回

  []

  。

  这个错误就是为什么结果中的某些条目总和不等于目标值的原因。

• 您已将

  result

  变量隐式定义为 global 变量，这将带来严重破坏：现在递归调用将重置调用者想要构建的数组，并用不同的值填充它条目。您应该使用

  result

  （或 const）将

  let

  定义为

  local

  变量。

  此错误还会导致结果中的某些条目总和不等于目标值。

• for

  循环将使您按所有顺序访问所有组合，但这意味着您将访问重复的组合。例如，根据问题中给出的“唯一”的定义，[1,2,3]和[3,2,1]是相同的组合。为了避免此类重复，请确保仅从数组中从上次选择位置开始的部分中选择候选值。这实际上意味着您可以跳过

  for

  循环，只对

  i

  等于 0 执行该逻辑。

不是问题，但是代码注释

// ignore the element

放置在错误的位置。应该再多放一行。

因此，通过尽可能少的更改，您的代码可以更正为：

var combinationSum = function(candidates, target) {
    if (target == 0) return [[]];
    if (candidates.length == 0) return []; // Moved here, and returning no solution.
    if (target < 0) return [];
    const result = []; // This should not be a global variable
    // Removed loop: Don't allow values to be taken in any order.
    let i = 0;
    let arr = [...candidates]
    // take the element
    let result1 = combinationSum([...candidates], target-candidates[i])
    result1.forEach((e)=>{e.push(candidates[i])})
    // ignore the element (this comment appeared at the wrong line)
    let result2 = combinationSum(arr.slice(0, i).concat(arr.slice(i + 1)), target)
    result.push(...result1, ...result2)
    return result
};

当然，你可以稍微清理一下代码，因为现在你不需要

i

；

slice

可以简化；

result

变量并不是真正需要的，因为您可以立即返回

result1

和

result2

的串联； ...等等。