javascript - 组合和编码挑战

我试图解决一个编码难题“组合和”（https://leetcode.com/problems/combination-sum/discuss/127208/Simple-Javascript-Solution）并找到了一个解决方案，但我不明白为什么需要currArr.pop()内部的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));

最佳答案

这种技术叫做回溯。
回溯是一种用于逐步建立问题解决方案的技术这些“部分解”可以用一系列决定来表达。一旦确定“部分解”不可行（即没有后续决策可以将其转换为解决方案），则回溯算法将其步骤返回到最后一个可行的“部分解”并重试。
这里的关键点是，在currArr.push（候选者[i]）之后，流是递归调用innerFunction（currArr，newTarget，i）；因此currArr不断增长，在某个点上，如果（target==0）找到了所需的结果，并且使用currArr.slice（）和return对currArr进行深度复制代码返回currArr.pop（）一步，因为这是在innerFunction递归调用之后。
我希望这能帮助你-）