计算机视觉技术 Opencv 控制跳转 Apache Pivot教程 typora xcode woocommerce extjs Component Validator vue标签 管理后台模板 安卓项目实战 android实战项目 jquery获取下一个元素 teamviewer验证被拒绝 oracle删除字段sql android常用布局 不用u盘装双系统 oracle重命名表名 plsql连接mysql数据库 docker保存镜像 python集合 python调用函数 python命令行参数 python加入环境变量 java案例 java环境安装 java数组追加 java路径 网页游戏开发入门 超级力量2修改 oem修改器 gg修改器下载 go程序设计语言 火萤壁纸下载 还原软件哪个好 早早省 python列表求和 deepcopy
当前位置: 首页 > 学习教程  > 编程语言

leetcode刷题记录17——组合综合II

2021/1/13 20:02:59 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

难度:中等 给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 说明: 所有数字(包括目标数)都是正整数。 …

难度:中等

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

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

说明:

所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。 
示例 1:

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

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


来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路:

和前一题的区别是这个不重复,剪枝要跳过同层相同的值

JavaScript解法:

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    candidates.sort((a,b) => a - b ); // 升序排序
    const res = [];

  const dfs = (start, temp, sum) => { // start是当前选择的起点索引 temp是当前的集合 sum是当前求和
    if (sum >= target) {
      if (sum == target) {
        res.push(temp.slice());  temp是引用,所指向的内存后续还要操作,所以拷贝一份
      }
      return;   // 结束当前递归
    }
    for (let i = start; i < candidates.length; i++) { // 枚举当前可选的数,从start开始
    if(i-1>=start&&candidates[i-1]===candidates[i]){//i-1至少要从当前start的往后,并且如果和左邻项值重复,就跳过
        continue;
    }
      temp.push(candidates[i]);          // 选这个数
      dfs(i+1, temp, sum + candidates[i]); // 基于此继续选择,传i,下一次就不会选到i左边的数
      temp.pop();   // 撤销选择,回到选择candidates[i]之前的状态,继续尝试选同层右边的数
    

    }
  };
  dfs(0, [], 0); // 最开始可选的数是从第0项开始的,传入一个空集合,sum也为0
  return res;
};

 


本文链接: http://www.dtmao.cc/news_show_600237.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?