数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究使用 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
广告