40、组合总和|40、组合总和 II | 算法（leetode，附思维导图 + 全部解法）300题 40、组合总和II|算法（leetode，

零标题 & 简介 1 标题
算法（leetode，附思维导图 + 全部解法）300题之（40）组合总和 II
2 简介
码农三少，一个致力于编写极简、但齐全题解（算法）的博主。
专注于一题多解、结构化思维，一起刷穿 LeetCode ~
一题目描述
文章图片

文章图片

二解法总览（思维导图） 【40、组合总和|40、组合总和 II | 算法（leetode，附思维导图 + 全部解法）300题】
文章图片

三全部解法 1 方案1
1)代码：

// 方案1 ”回溯法（递归版）“ // 通过：172 / 175。输入 [1, 1, ... , 1, 1] 时会超时！！// 技巧：“有序胜过无序”。 // 通过sort方法（时间复杂度仅为 O(nlogn)）将无序的数组变有序是一件很划算的事情。// 思路： // 1）状态初始化 // 2）调用 dfs // 3）结果去重 // 4）返回结果 resList var combinationSum2 = function(candidates, target) { const dfs = (curIndex, l, curSum, target, curArr, resList) => { // 1）递归出口 if (curSum === target) { // 注：使用 slice ，取得其副本值！！ resList.push(curArr.slice()); return; } if (curIndex >= l || curSum > target) { return; }// 2）递归主体（回溯 = 选 + 不选） // 2.1）选 curArr.push(candidates[curIndex]); curSum += candidates[curIndex]; dfs(curIndex + 1, l, curSum, target, curArr, resList); // 2.1）不选（注：可能需要恢复环境，如下面的2行代码 —— pop、-= ） curArr.pop(); curSum -= candidates[curIndex]; dfs(curIndex + 1, l, curSum, target, curArr, resList); }; // 1）状态初始化 const l = candidates.length; candidates = candidates.sort((a, b) => a - b); let curIndex = 0, curSum = 0, curArr = [], resList = []; // 2）调用 dfs dfs(curIndex, l, curSum, target, curArr, resList); // 3）结果去重 resList = [...new Set(resList.map(item => item.join('#')))].map(item => item.split('#')); // 4）返回结果 resList return resList; };

2 方案2
1)代码：

// 方案2 ”回溯法（递归版 - 优化）“// 思路： // 1）状态初始化 // 2）调用 dfs // 3）返回结果 resList// 参考： // 1）https://leetcode-cn.com/problems/combination-sum-ii/solution/man-tan-wo-li-jie-de-hui-su-chang-wen-shou-hua-tu-/ const combinationSum2 = (candidates, target) => { // 1）状态初始化 const l = candidates.length; candidates = candidates.sort((a,b) => a - b ); const resList = []; const dfs = (curIndex, curArr, sum) => { // start是索引当前选择范围的第一个 // 1）递归出口 if (sum === target) { // 注：使用 slice ，深拷贝！ resList.push(curArr.slice()); return; } if (sum > target) { return; }// 2）递归主体 // 枚举出当前的选择 for (let i = curIndex; i < l; i++) { // 边界：当前选项和左邻选项一样，跳过！ if (i - 1 >= curIndex && candidates[i - 1] == candidates[i]) { continue; } // 2.1）选择 curArr.push(candidates[i]); dfs(i + 1, curArr, sum + candidates[i]); // 2.2）不选 curArr.pop(); } }; // 2）调用 dfs dfs(0, [], 0); // 3）返回结果 resList return resList; };

四更多 1 刷题进度

1）LeetCode：347 / 2491 。2）《剑指offer》：66 / 66 。3）相关学习资料与笔记汇总： https://github.com/CYBYOB/algorithm-leetcode/tree/master/资料%26笔记。4）注：所有题目均有 2-5种左右的解法，后续还将不断更新题目 & 题解。敬请期待~ 也欢迎大家进群一起学习、交流、刷题&拿高薪~

40、组合总和|40、组合总和 II | 算法（leetode，附思维导图 + 全部解法）300题

文章图片

2 GitHub - LeetCode项目仓库

0）本项目地址： https://github.com/CYBYOB/algorithm-leetcode 。目标、愿景：让每个人都能拥有一定的算法能力、以应对面试中（会举一反三的同学还可以将其融入自己的肌肉和血液，甚至能够赋能于公司的业务和技术）的算法。本人每周仍在不断的更新 —— 保证每周都有新的题目、题解方案刺激着您的神经和刷题欲望。欢迎对算法感兴趣的同学加入我们的社群。 QQ群： 933919972 ；作者QQ： 1520112971 ；作者VX： c13227839870（可拉您进群、一起学习与交流~）。

文章图片

文章图片

3 作者标签

1）“BAT里1名小小的伪全栈工程师，主攻前端，偶尔写点后端”。2）2019年的微信小程序应用开发赛 - 全国三等奖； 2019CODA比赛 - 前 17/211 强且荣获“优秀团队”称号等。3）“半自媒体人”，在校期间、个人公众号（IT三少。新自媒体（公众号）号：码农三少）在半年内实现了0到5.8K+的粉丝增长等。