DFS Combination Sum, How to get only unique results?

user_5092005 0
Viewed 212

I am solving LeetCode #49 Combination Sum. The idea is to find all the unique combinations that sum to the target.

It's fairly straight forward to find the permutations that add to the sum but I'm stuggling to modify my code to only find unique permutations.

What is the general concept in dynamic programming for getting the unique results with recursion?

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

Input:

[2,3,6,7]
7

My Output:

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

Desired Output:

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

How do I avoid duplicates?

dynamic-programming recursion javascript
2 Answers

A simple way to handle this is to split the recursion into two cases, one where we use the first candidate and one where we don't. In the first case, we reduce the total we need to reach. In the second, we shrink the number of candidates available. That means we need at least two base cases, when the total is zero and when the number of candidates reaches to zero (here we also handle the case where the total is less than zero.) Then the recursive calls become pretty clean:

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)

user_12436410

You need an index to make sure the same combination (different order) is not repeated again and start your loop from the index.

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

This index needs to be passed inside your recursive function (I have changed it to for loop to make it more readable)

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

Working Code below:

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);

user_26926880
Related