DFS组合和，如何只得到唯一的结果？

Question

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

找到添加到总和的排列相当简单，但我正在努力修改我的代码以仅找到唯一的排列。

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

/**
 * @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

您需要 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);

Answer 2

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

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)

DFS组合和，如何只得到唯一的结果？

DFS Combination Sum, How to get only unique results?

javascript

recursion

dynamic-programming