网站主机空间用哪个好,论坛网站备案,民法典建设工程施工合同,蚌埠网站制作理论基础
代码随想录原文
什么是回溯法
回溯也可以叫做回溯搜索法#xff0c;它是一种搜索的方式。
回溯是递归的副产品#xff0c;只要有递归就会有回溯。
回溯法的效率
虽然回溯法很难#xff0c;不好理解#xff0c;但是回溯法并不是什么高效的算法。因为回溯的本…理论基础
代码随想录原文
什么是回溯法
回溯也可以叫做回溯搜索法它是一种搜索的方式。
回溯是递归的副产品只要有递归就会有回溯。
回溯法的效率
虽然回溯法很难不好理解但是回溯法并不是什么高效的算法。因为回溯的本质是穷举穷举所有可能然后选出我们想要的答案。如果想让回溯法高效一些可以加一些剪枝的操作但也改变不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢
因为没得选一些问题能暴力搜出来就不错了撑死了再剪枝一下还没有更高效的解法。
回溯法解决的问题
回溯法一般可以解决如下几种问题
组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构。
因为回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度。
递归就要有终止条件所以必然是一棵高度有限的树N叉树。
回溯法模板
回溯法三部曲第一步是确定回溯函数的额返回值和参数第二步是确定回溯函数的终止条件第三步是去顶回溯搜索的遍历过程具体如下
回溯函数模板返回值以及参数
回溯算法中函数返回值一般为void。
再来看一下参数因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来所以一般是先写逻辑然后需要什么参数就填什么参数。
回溯函数的伪代码如下
void backtracking(参数)回溯函数终止条件
什么时候达到了终止条件树中就可以看出一般来说搜到叶子节点了也就找到了满足条件的一条答案把这个答案存放起来并结束本层递归。
所以回溯函数终止条件伪代码如下
if (终止条件) {存放结果;return;
}回溯搜索的遍历过程
在上面我们提到了回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成了树的深度。
如下图 注意图中集合大小和孩子的数量是相等的
回溯函数遍历过程伪代码如下
for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果
}for循环就是遍历集合区间可以理解一个节点有多少个孩子这个for循环就执行多少次。
backtracking这里自己调用自己实现递归。
可以看出for循环可以理解是横向遍历backtracking递归就是纵向遍历这样就把这棵树全遍历完了一般来说搜索叶子节点就是找的其中一个结果。
回溯算法模板框架如下
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}77. 组合
题目链接108.将有序数组转换为二叉搜索树
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 文章讲解/视频讲解https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html 思路
按照顺序将所有可能的结果加进去例如对于n 4, k 2的题设可以顺序将[1, 2]、[1, 3]、[1, 4]、[2, 3]、[2, 4]、[3, 4]添加进结果中。
代码的实现按照回溯模板来做
首先确定backtracking的模板参数需要传入一个存储当前组合的数组combine当前遍历到的整数i题目给定的最大整数n和每个组合的大小k。
回溯的终止条件当然是combine数组的大小等于k的时候将combine数组加入最终结果results中并返回。
遍历过程对于当前遍历到的整数i我们对i及之后的数连续遍历加入combine数组并递归地对需要添加的下一个数进行处理具体见代码。
看了卡哥的教程之后发现这道题可以进行剪枝优化。举一个例子n 4, k 4的话那么第一层for循环的时候从元素2开始的遍历都没有意义了。在第二层for循环的时候从元素3开始的遍历都没有意义了。如下图 可以优化的点就在于约束每一层for循环的范围。对于我的代码而言当前遍历的整数为j从j到n剩余的整数数量为n - j 1组合中还需要的元素个数为k - combine.size()为了保证此次遍历最终能够添加到新的组合n - j 1需要大于等于k - combine.size()即 n − j 1 ≥ k − c o m b i n e . s i z e ( ) j ≤ n 1 − k c o m b i n e . s i z e ( ) n - j 1 \geq k - combine.size()\\ j \leq n 1 - k combine.size() n−j1≥k−combine.size()j≤n1−kcombine.size()
C实现
class Solution {
public:vectorvectorint results;vectorvectorint combine(int n, int k) {vectorint combine;backtracking(combine, 1, n, k);return results;}void backtracking(vectorint combine, int i, int n, int k){if(combine.size() k){results.push_back(combine);return;}for(int j i;jn;j){combine.push_back(j);backtracking(combine, j 1, n, k);combine.pop_back();}}
};// 剪枝的代码
class Solution {
public:vectorvectorint results;vectorvectorint combine(int n, int k) {vectorint combine;backtracking(combine, 1, n, k);return results;}void backtracking(vectorint combine, int i, int n, int k){if(combine.size() k){results.push_back(combine);return;}for(int j i;jn 1 - k combine.size();j){combine.push_back(j);backtracking(combine, j 1, n, k);combine.pop_back();}}
};
