leetcode刷题总结之回溯法

leetcode刷题总结之回溯法"/>

leetcode刷题总结之回溯法

前言：

今天是2022/2/11，对以前自己总结的回溯法文章进行重写，在网上看了一些文章，无脑刷了很多回溯题，有些相同的套路总结下，便于自己以后能快速复习。

文章目录

• 0x01）回溯法与 dfs 的区别
• 0x02）回溯法可解决的问题
• 0x03）回溯法编码步骤
• 0x04）习题解析
• • 4.1）排列问题
  • 4.2）子集问题

0x01）回溯法与 dfs 的区别

回溯法是枚举所有的搜索路径，并把这些搜索路径都记录下来，当到达递归树中的某个节点发现该节点无效或者寻找到问题的可行解时，就回退到上一步，将之前选择的边进行 pop_back，然后尝试下一条搜索路径。

当回溯用于树的时候，就是深度优先搜索。当然了，几乎所有可以用回溯解决的问题都可以画递归树。那么这俩在这里就几乎同义了。如果一个问题解决的时候显式地使用了树，那么我们就叫它 dfs。很多时候没有用树我们也管它叫 dfs 严格地说是不对的，至于回溯和 dfs 都可以使用剪枝。

0x02）回溯法可解决的问题

1）全排列问题：N 个数按一定的规则进行全排列，有几种排列方式。
2）子集问题：一个 N 个数的集合中有多少符合条件的子集。
3）组合问题：其实也是子集问题，只不过要求子集中的元素个数为 k 且满足一定条件。
4）分割问题：一个字符串按一定的规则有几种切割方式。
5）棋盘问题：N 皇后、黄金矿工、数独。

0x03）回溯法编码步骤

1）画递归树：画递归树，找到状态变量（这个状态变量是指控制当前层该节点的选择列表的）。
2）找终止条件：判断此时的路径是否可以作为结果。
3）找选择列表：找准选择列表就要搞懂状态变量是如何变化的，如何确定呢？直接画递归树，确定当前层到下一层的新的选择列表。
4）是否剪枝：判断是否需要剪枝（是否所有答案都满足题目要求，是则无需剪枝，不是则确定剪枝条件）
5）做出选择并递归进入下一层：使用 for 循环从选择路径中做出选择，调用递归函数进入下一层
6）撤销选择：从下层函数返回后，撤销这次的路径选择，从同一层做出其他选择。

总结下：设计回溯的参数就是看递归树中，当前层的节点到达下一层的节点时，下一层节点的选择列表是怎么样的！像子集问题是当前层节点选择下标 i，那么下一层的选择列表为[i+1,n-1]了，当前层的选择列表为[start,n-1]，枚举每个 a[i] 作为子集的起点。

回溯法的框架：

//choicelist：表示可以进行选择的列表，相当于树中可选用左节点还是右节点
//path：表示为决策路径,相当于在解空间树中为根节点到某个叶子节点的路径
//res：表示存放根节点到所有叶子节点的所有路径，所有可行解
backtrack(choicelist,path,res)
{if(path is ok)res.push_back(path);//找到一个可行解for(当前层选择列表:i){// 路径上加入选择 ipath_back(i);// 进入下一层的节点backtrack(new_choicelist,path,res);// 返回当前层即撤销之前进入下一层的选择，从for开始重新做选择path.pop_back();}
}

回溯法的时间复杂度：

• 对于像0/1背包这种问题，每次要做的决策是选或不选，相应的解空间树为子集二叉树，共2^(n+1)-1==叶子节点，所以时间复杂度为O(2^n)。
• 对于像全排列这种问题，每次要做的决策是还剩下的列表选一个数字，相应的解空间树为排列树，共n!个叶子节点，所以时间复杂度为O(n!)。
• 注：无论是子集树还是排列树，不过就是可选择的列表不一样罢了。

0x04）习题解析

4.1）排列问题

46. 全排列：用一个 bool 型数组 v 来标记每个节点的选择列表，进入下一层时，标记 v[i]=1，然后从下一层的节点中选择列表进行做选择，直到到达叶子节点也就是选择列表为空即path的大小为n，然后开始回溯，返回到上一层即可。

47. 全排列 II：在上一题的基础上，加入去重即可，将数组排序使相同值得元素相邻，从当前层做选择进入下一层节点时，要保证相同元素只使用一次，同层相同元素使用多次，剩下的元素全排列必然重复，用来剪枝即可。

4.2）子集问题

回溯的很多问题都是枚举子集问题，当前层进入下一层是以 a[i] 作为起点，进入下一层的节点的选择列表为[i+1,n-1]，所以回溯的参数为 start，for选择的范围为[start,n-1]，当前层选择 a[i] 时，[start,i-1]之前的元素已经作为子集的起点枚举过了不用管了，每进入一层添加这层的所有路径即可。

78. 子集：注意当前层的选择列表为[start,n-1]，选择 a[i] 进入下一层后选择列表变为[i+1,n-1]了。

90. 子集 II：与上一题相比多了剪枝，是因为重复元素作为起点必然造成重复子集，和47. 全排列 II一样先将数组排序，然后当前层的 for 循环，剪枝重复元素即可。