使用 JavaScript 的组合和问题

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/2/21 9:48:17

假设我们给出了一组候选数字(没有重复)和一个目标数字(目标)。

我们需要编写一个函数，在候选数字中找到所有唯一组合，其中候选数字的总和等于目标。

可以从候选数字中选择相同的重复数字，次数不限。

注意 −

所有数字(包括目标)都将是正整数。
解决方案集不得包含重复的组合。

例如 −

如果输入是 −

candidates = [2,3,6,7], target = 7,

解决方案可以是 −

[
   [7],
   [2,2,3]
];

由于问题是获取所有可能的结果，而不是最佳结果或结果数量，因此我们不需要考虑动态规划，需要使用递归的回溯方法来处理它。

示例

以下是代码 −

const recursiveSum = (
   candidates,
   remainingSum,
   finalCombinations = [],
   currentCombination = [],
   startFrom = 0,
) => {
   if (remainingSum < 0) {
      return finalCombinations;
   }
   if (remainingSum === 0) {
      finalCombinations.push(currentCombination.slice());
      return finalCombinations;
   }
   for (let candidateIndex = startFrom; candidateIndex < candidates.length; candidateIndex += 1) {
      const currentCandidate = candidates[candidateIndex];
      currentCombination.push(currentCandidate);
      recursiveSum(
         candidates,
         remainingSum - currentCandidate,
         finalCombinations,
         currentCombination,
         candidateIndex,
      );
      currentCombination.pop();
   }
   return finalCombinations;
}
const combinationSum = (candidates, target) => recursiveSum(candidates, target);
console.log(combinationSum([2, 3, 6, 7], 7));