Блог

Я решаю комбинационную сумму кода #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]]
 

Как мне избежать дублирования?

Простой способ справиться с этим-разделить рекурсию на два случая, в одном из которых мы используем первого кандидата, а в другом-нет. В первом случае мы уменьшаем общее количество, которого нам нужно достичь. Во-вторых, мы сокращаем количество доступных кандидатов. Это означает, что нам нужны по крайней мере два базовых случая, когда общее число равно нулю и когда число кандидатов достигает нуля (здесь мы также рассматриваем случай, когда общее число меньше нуля). Тогда рекурсивные вызовы становятся довольно чистыми:

 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) 

Вам нужно 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);