组合和编码挑战

Question

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

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是不断增长的，在某个时候，如果(目标=== 0(期望的结果已经找到，并且你使用currArr.slice((对currArr进行深度复制，现在使用return，代码回到currArr.pop((1步，因为这是在innerFunction递归调用之后。

我希望这可以帮助您 - (