DFS组合求和，如何得到唯一的结果?

Question

我正在解LeetCode #49组合和。这个想法是找到所有唯一的组合，和目标。

找到加到总和中的排列是相当直接的，但我正在努力修改我的代码以只找到唯一的排列。

在动态规划中获得递归唯一结果的一般概念是什么?

/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let distinct = []
let dfs = (candidates, target, list = []) => {
if (target === 0) {
distinct.push(list)
return
}
candidates.forEach((candidate, i) => {
let diff = target - candidate;
if (diff >= 0) {
dfs(candidates, diff, [...list, candidate])
}
})
}
dfs(candidates, target)
return distinct
};

输入:

[2,3,6,7]
7

我输出:

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

所需输出:

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

如何避免重复?

Answer 1

处理这个问题的一个简单方法是将递归分为两种情况，一种是使用第一个候选项，另一种是不使用。在第一种情况下，我们减少我们需要达到的总数。在第二种情况下，我们减少可用的候选人数量。这意味着我们至少需要两个基本情况，即当总数为零和当候选数量达到零时(这里我们还处理总数小于零的情况)。然后递归调用变得非常干净:

const combos = (cs, t) =>
cs .length == 0 || t < 0
? []
: t == 0
? [[]]
: [
... combos (cs, t - cs [0]) .map (sub => [cs [0], ...sub]), // use cs [0]
... combos (cs .slice (1), t)                               // don't use it
]
const display = (cs, t) => 
console .log (`combos (${JSON.stringify(cs)}, ${t}) => ${JSON.stringify(combos(cs, t))} `)
display ([2, 3, 6, 7], 7)
display ([2, 3, 5], 8)
display ([8, 6, 7], 42)

Answer 2

您需要一个index来确保相同的组合(不同的顺序)不会再次重复，并从索引开始循环。

let dfs = (candidates, target, list = [], index = 0) => {

这个索引需要在递归函数内部传递(我已经将其更改为for循环以使其更具可读性)

for (let i = index; i < candidates.length; i++) {
......
dfs(candidates, diff, [...list, candidates[i]], i)

---

下面的工作代码:

var combinationSum = function(candidates, target) {
let distinct = []
// add index in your function
let dfs = (candidates, target, list = [], index = 0) => {
if (target === 0) {
distinct.push(list)
return
}
for (let i = index; i < candidates.length; i++) {
let diff = target - candidates[i];
if (diff >= 0) {
//pass index as your current iteration
dfs(candidates, diff, [...list, candidates[i]], i)
}
}
}
dfs(candidates, target)
console.log(distinct);
};

combinationSum([2, 3, 6, 7], 7);