Open evenMai92 opened 3 years ago
参考一 参考二 参考三 「回溯是递归的副产品,只要有递归就会有回溯」,所以回溯法也经常和二叉树遍历,深度优先搜索混在一起,因为这两种方式都是用了递归。
回溯法就是暴力搜索,并不是什么高效的算法,最多再剪枝一下。
回溯算法能解决如下问题:
回溯法的模板:
backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) { 处理节点; backtracking(路径,选择列表); // 递归 回溯,撤销处理结果 } }
子集问题
子集问题(一) 「本题其实可以不需要加终止条件」,因为start >= nums.length,本层for循环本来也结束了,本来我们就要遍历整颗树。
并不会无限递归,因为每次递归的下一层就是从i+1开始的。
如果要写终止条件,注意:result.push(nums[i]);要放在终止条件的上面,如下:
const res = []; // 结果 function subsets(nums) { if(nums.length === 0) return null; const temp = []; // 缓存结果值 backtracking(0, nums, temp); return res; } function backtracking(start, nums, temp) { res.push([...temp]);; // 收集子集,要放在终止添加的上面,否则会漏掉结果 if (start>= nums.length) { // 终止条件可以不加 return; } // 从start开始遍历,避免重复 for(let i = start; i < nums.length; i++) { // 处理节点; temp.push(nums[i]); // 递归 backtracking(i + 1, nums, temp); // 回溯 temp.pop(); } } subsets([1,2,3])
子集问题(二) 这个题目与前面的子集题目相比较,差别就在于包含重复的子集,也就是不能顺序改变而已,元素一样的子集出现。
这个题目框架还是不变的,但是,要做一下简单的剪枝操作:怎么排除掉重复的子集。
这里我通过Map数据结构来去重,如下:
const res = []; // 结果 const map = new Map(); // 用来判断是否重复 function subsets(nums) { if(nums.length === 0) return null; const temp = []; // 缓存结果值 backtracking(0, nums, temp); return res; } function backtracking(start, nums, temp) { // 去重 if(!map.has(temp.join())) { res.push([...temp]);; // 收集子集,要放在终止添加的上面,否则会漏掉结果 map.set(temp.join(), temp); } // 从start开始遍历,避免重复 for(let i = start; i < nums.length; i++) { // 处理节点; temp.push(nums[i]); // 递归 backtracking(i + 1, nums, temp); // 回溯 temp.pop(); } } subsets([1,1,2])
全排列问题
全排列问题(一)
排列是有序的,也就是说[1,2] 和[2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用start了,而且我们这边还要进行剪枝(temp集合中有的就排除)。如下:
const res = []; // 结果 function subsets(nums) { if(nums.length === 0) return null; const temp = []; // 缓存结果值 backtracking(0, nums, temp); return res; } function backtracking(start, nums, temp) { // 终止条件 if(nums.length === temp.length) { res.push([...temp]); return; } // 从0开始遍历 for(let i = 0; i < nums.length; i++) { // 去重 if(temp.includes(nums[i])) { continue; } // 处理节点; temp.push(nums[i]); // 递归 backtracking(i + 1, nums, temp); // 回溯 temp.pop(); } } subsets([1,2,3])
组合问题
组合问题(一) 可以直观的看出其搜索的过程:「for循环横向遍历,递归纵向遍历,回溯不断调整结果集」
其中优化回溯算法只有剪枝一种方法,在回溯算法:组合问题再剪剪枝中把回溯法代码做了剪枝优化,树形结构如图: 「回溯算法:求组合问题!剪枝精髓是:for循环在寻找起点的时候要有一个范围,如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了,就没有必要搜索了」。
「在for循环上做剪枝操作是回溯法剪枝的常见套路!」,如下。
const res = []; // 结果 function subsets(nums, k) { if(nums.length === 0) return null; const temp = []; // 缓存结果值 backtracking(0, nums, k, temp); return res; } function backtracking(start, nums, k, temp) { if(k === temp.length) { res.push([...temp]); return; } // 从start开始遍历,无优化版 i < nums.length // 剪枝优化 i < (nums.length - (k - temp.length) + 1) for(let i = start; i < (nums.length - (k - temp.length) + 1); i++) { // 处理节点; temp.push(nums[i]); // 递归 backtracking(i + 1, nums, k, temp); // 回溯 temp.pop(); } } subsets([1,2,3,4], 2);
组合总和(一) 这个题目跟之前的没有什么太大的区别,只是需要注意一个点:每个数字可以被无限制重复被选取,我们要做的就是在递归的时候,i的下标不是从i+1开始,而是从i开始。
const res = []; // 结果 function subsets(nums, target) { if(nums.length === 0) return null; const temp = []; // 缓存结果值 backtracking(0, nums, target, temp); return res; } function backtracking(start, nums, target, temp) { // 终止条件 if(target < 0) { return; } // 获取结果 if(target === 0) { res.push([...temp]); } // 从start开始遍历 for(let i = start; i < nums.length; i++) { // 处理节点; temp.push(nums[i]); // 递归 backtracking(i, nums, target - nums[i], temp); // 回溯 temp.pop(); } } subsets([2,3,6,7], 7);
组合总和(二) 题目差不多,只不过这里只是每个数字只能用一次,同时也是不能包含重复的组合,所以,用之前Map去重方法解决.
const res = []; // 结果 const map = new Map(); function subsets(nums, target) { if(nums.length === 0) return null; const temp = []; // 缓存结果值 backtracking(0, nums.sort(), target, temp); return res; } function backtracking(start, nums, target, temp) { // 终止条件 if(target < 0) { return; } // 获取结果(判断是否重复) if(target === 0 && !map.has(temp.join())) { res.push([...temp]); map.set(temp.join(), temp); } // 从start开始遍历 for(let i = start; i < nums.length; i++) { // 处理节点; temp.push(nums[i]); // 递归 backtracking(i + 1, nums, target - nums[i], temp); // 回溯 temp.pop(); } } subsets([10,1,2,7,6,1,5], 8);
参考一 参考二 参考三 「回溯是递归的副产品,只要有递归就会有回溯」,所以回溯法也经常和二叉树遍历,深度优先搜索混在一起,因为这两种方式都是用了递归。
回溯法就是暴力搜索,并不是什么高效的算法,最多再剪枝一下。
回溯算法能解决如下问题:
回溯法的模板:
子集问题
子集问题(一) 「本题其实可以不需要加终止条件」,因为start >= nums.length,本层for循环本来也结束了,本来我们就要遍历整颗树。
并不会无限递归,因为每次递归的下一层就是从i+1开始的。
如果要写终止条件,注意:result.push(nums[i]);要放在终止条件的上面,如下:
子集问题(二) 这个题目与前面的子集题目相比较,差别就在于包含重复的子集,也就是不能顺序改变而已,元素一样的子集出现。
这个题目框架还是不变的,但是,要做一下简单的剪枝操作:怎么排除掉重复的子集。
这里我通过Map数据结构来去重,如下:
全排列问题
全排列问题(一)
排列是有序的,也就是说[1,2] 和[2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用start了,而且我们这边还要进行剪枝(temp集合中有的就排除)。如下:
组合问题
组合问题(一) 可以直观的看出其搜索的过程:「for循环横向遍历,递归纵向遍历,回溯不断调整结果集」
其中优化回溯算法只有剪枝一种方法,在回溯算法:组合问题再剪剪枝中把回溯法代码做了剪枝优化,树形结构如图: 「回溯算法:求组合问题!剪枝精髓是:for循环在寻找起点的时候要有一个范围,如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了,就没有必要搜索了」。
「在for循环上做剪枝操作是回溯法剪枝的常见套路!」,如下。
组合总和(一) 这个题目跟之前的没有什么太大的区别,只是需要注意一个点:每个数字可以被无限制重复被选取,我们要做的就是在递归的时候,i的下标不是从i+1开始,而是从i开始。
组合总和(二) 题目差不多,只不过这里只是每个数字只能用一次,同时也是不能包含重复的组合,所以,用之前Map去重方法解决.