使用 JavaScript 组合求和问题

假设我们给定了一组候选数字（无重复数字）和一个目标数字（target）。

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

可以从候选数字中无限次地选取同一个重复数字。

注意 −

  • 所有数字（包括目标数字）都将是正整数。

  • 解决方案集中不得包含重复的组合。

例如 −

如果输入为 −

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));

输出

在控制台上输出如下 −

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

更新于: 11-12-2020

457 Views

加速您的 职业生涯

完成课程获得认证

开始
广告