我正在解決LeetCode #49 Combination Sum問題。我們的想法是找到所有與目標相加的獨特組合。
找到與總和相加的排列組合是相當直接的，但是我正在努力修改我的代碼，以便只找到唯一的排列組合。
在動態編程中，通過遞回獲得唯一結果的一般概念是什么？
/**。
* @param {number[]}。候選者。
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function （candidates, target） {
let distinct = [] [
let dfs = (candidates, target, list = []/span>) => {
if (target ==0) {
distinct.push(list)
回傳。
}
candidates.forEach((candidate, i) =>/span> {
let diff = target - candidate;
if (diff >= 0) {
dfs(candents, diff, [...list, candidate])
}
})
}
dfs(candents, target)
return distinct
};
輸入：
[2,3,6,7]
7]。
我的輸出：
[[2,2,3]，[2, 3,2], [3, 2,2], [7]]
期望的輸出：
[[2,2,3],[7] ]
我如何避免重復？
uj5u.com熱心網友回復：
處理這個問題的簡單方法是將遞回分成兩種情況，一種是我們使用第一個候選人，另一種是我們不使用。 在第一種情況下，我們減少我們需要達到的總數。 在第二種情況下，我們縮小了可用的候選人數量。 這意味著我們至少需要兩種基本情況，當總數為零時，以及當候選人的數量達到零時（這里我們也處理總數小于零的情況）。
。const combos = （cs, t） =>
cs .length == 0 || t < 0 ?
? []
: t == 0 ?
? [[]]
: [
... combos (cs, t - cs [0] ) 。 map (span class="hljs-params">sub => [cs [0], ...sub]), // use cs [0]
... combos (cs .slice (1), t) //不使用它。
]
const display = (cs, t) =>
console .log (`combos (${JSON. stringify(cs)}, ${t}) => ${JSON.stringify(combs(cs, t))} `)
display ([2, 3, 6, 7], 7)
顯示（[2, 3, 5], 8)
顯示（[8, 6, 7], 42）uj5u.com熱心網友回復：
你需要一個index以確保相同的組合（不同的順序）不會再次重復，并從索引開始你的回圈。
let dfs = （candidates, target, list = [], index = 0) => {
這個索引需要在你的遞回函式里面傳遞（我把它改成了for回圈，使它更易讀）
for (let i = index; i < candidates.length; i ) {
......
dfs(candates, diff, [...list, candidates[i]], i)
作業代碼
下面的作業代碼：
標籤：var combinationSum = function(candidates, target) {
let distinct = [] [
//在你的函式中添加索引。
let dfs = (candidates, target, list = [] , index = 0) => {
if (target == 0) {
distinct.push(list)
回傳。
}
for (let i = index; i < candidates.length; i ) {
let diff = target - candidates[i];
if (diff >= 0) {
//pass index as your current iteration[/span].
dfs(candates, diff, [...list, candidates[i]], i)
}
}
}
dfs(candents, target)
console.log（distinct）。
};
combinationSum([ 2, 3, 6, 7], 7）。)