資料結構
網路
關係型資料庫管理系統
作業系統
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
廣告