javascript - 组合和编码挑战

Question

我正在尝试解决编码挑战“组合和”(https://leetcode.com/problems/combination-sum/discuss/127208/Simple-Javascript-Solution)并找到了解决方案，但我不明白为什么 if (target > = candidates[i]) 是必需的。我试图通过删除并替换它来理解，但仍然无法弄清楚。有人可以解释为什么这对我来说是必要的吗？谢谢!

var combinationSum = function(candidates, target) {
  candidates.sort((a,b) => a - b);
  const results = [];


  const innerFunction = (currArr, target, index) => {
    
    if (target === 0) {
      results.push(currArr.slice());
      return;
    }

    for (let i = index; i < candidates.length; i++) {

      if (target >= candidates[i]) {
        
        const newTarget = target - candidates[i];
        currArr.push(candidates[i]);
        innerFunction(currArr, newTarget, i);
        currArr.pop();
      
      } else {

        return;

      }
    }

  }


  innerFunction([], target, 0);
  return results;
};

console.log(combinationSum([2,3,6,7], 7));

Answer 1

这种技术称为回溯。回溯是一种用于逐步构建问题解决方案的技术。这些“部分解决方案”可以用一系列决策来表述。一旦确定“部分解决方案”不可行(即没有后续决策可以将其转换为解决方案)，回溯算法就会回溯到最后一个可行的“部分解决方案”并再次尝试。

这里的关键点是在currArr.push(candidates[i])流程之后递归调用innerFunction(currArr, newTarget, i);所以 currArr 不断增长，在某个时候，如果 (target === 0) 找到了想要的结果，并且您使用 currArr.slice() 对 currArr 进行深度复制，现在返回，代码返回 currArr.pop( ) 因为这是在 innerFunction 递归调用之后发生的。

希望对你有所帮助-)