使用JavaScript的组合和问题

假设我们得到了一组候选编号（无重复）和一个目标编号(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 ] ]