2-10 - 40. 组合总和 II
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
解题思路
思路同组合1
解题代码
/** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum2 = function (candidates, target) { candidates.sort((a,b)=>a-b) let ans = []; let backTracing = (start, path, sum) => { if (sum >= target) { if (sum === target) { ans.push(path.slice()) } return } for (let i = start; i < candidates.length; i++) { if (i - 1 >= start && candidates[i - 1] == candidates[i]) { continue; } path.push(candidates[i]) backTracing(i + 1, path, sum + candidates[i]) path.pop() } } backTracing(0, [], 0) return ans };
2-11 - 47. 全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8
-10 <= nums[i] <= 10
## 解题思路
同上全排列
## 解题代码
var permuteUnique = function (nums) { let ans = []; let used = Array(nums.length).fill(false) let backTracing = (start, path) => { if (start === nums.length) { ans.push(path.slice()) return } for (let i = 0; i < nums.length; ++i) { if (used[i] || (i > 0 && nums[i] === nums[i - 1] && !used[i - 1])) { continue; } path.push(nums[i]) used[i] = true backTracing(start + 1, path) used[i] = false path.pop() } } nums.sort((a, b) => a - b) backTracing(0, []) return ans };
三、总结
主要运用了回溯算法；而解决一个回溯问题，实际上就是一个决策树的遍历过程。
3.1 模板
let backtracking=(路径，选择列表) =>{ if (满足结束条件)) { 存放路径; return; } for (选择：路径，选择列表) { 做出选择； backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
即:
- 1.路径：也就是已经做出的选择。
- 2.选择列表：也就是你当前可以做的选择。
- 3.结束条件：也就是到达决策树底层，无法再做选择的条件。
3.2 剪枝函数
- 1.用约束条件剪除得不到的可行解的子树
- 2.用目标函数剪取得不到的最优解的子树
3.3 回溯法的一般步骤：
- 1.设置初始化的方案（给变量赋初始值，读入已知数据等）
- 2.变换方式去试探，若全部试完侧转（7）
- 3.判断此法是否成功（通过约束函数），不成功则转（2）
- 4.试探成功则前进一步再试探
- 5.正确方案还是未找到则转（2）
- 6.以找到一种方案则记录并打印
- 7.退回一步（回溯），若未退到头则转（2）
- 8.已退到头则结束或打印无解
继续加油！！！
