ii组合总和_一天一大lee(组合总和II)难度:中等Day20200910

题目:

给定一个数组 candidates  和一个目标数  target 找出  candidates  中所有可以使数字和为  target  的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明

• 所有数字(包括 target)都是正整数。
• 解集不能包含重复的组合。

示例:

输入: candidates  [10,1,2,7,6,1,5], target  8,所求解集为:[  [1, 7],  [1, 2, 5],  [2, 6],  [1, 1, 6]]

输入: candidates  [2,5,2,1,2], target  5,所求解集为:[  [1,2,2],  [5]]

抛砖引玉

思路

本题逻辑的重点在不允许 candidates 的元素重复使用但是 candidates 元素本身可能存在重复元素

• candidates 中同一个元素不能在一种组合中重复使用
• 结果元素相同组成的子元素位置不同算作一种结果

day-08: 组合 (难度:中等)

day-09: 组合总和 (难度:中等)

在前两天的题目中分别用

两种形式处理了递归回溯子元素组合的问题

结合本题的要求

• 指针可以协助完成同一个元素不能在一种组合中重复使用
• 如果采用指针驱动的形式发现很难避免不同位置的元素形成相同元素的结果而采用约束区域来枚举元素的形状相同的元素(对 candidates 排序相邻元素相同)被指针约束则很好避免在不同个组合中信息相同个元素

实现

• 对 candidates 排序(将相同元素排列在一起方便指针控制元素不重复参与组合)
• 递归从i之后遍历为参与组合元素:
• 在i指针之后遇到相同元素则不再选择i处元素因为此时已回溯再次选择i处元素则形成了重复的组合

/** * param {number[]} candidates * param {number} target * return {number[][]} */var combinationSum2  function (candidates, target) {  let _result  []  candidates  candidates.sort((a, b) > a - b)  function dfs(i, item, sum) {    if (sum  target) {      _result.push(item)      return    }    for (let x  i; x       if (target - sum - candidates[x] > 0) {        // i指针所在元素如果后面还有与其相同的元素则不再选择i处元素因为此时已回溯再次选择i处元素则形成了重复的组合        if (x ! i  candidates[x - 1]) continue        item.push(candidates[x])        dfs(x  1, [...item], sum  candidates[x])        item.pop()      }    }  }  dfs(0, [], 0)  return _result}

博客: 小书童博客

每天的每日一题写的题解会同步更新到公众号一天一大 lee 栏目 欢迎关注留言

公号: 前端小书童