【算法刷题】回溯算法题型及方法归纳_回溯法求解sat问题例题

1、回溯算法特点

回溯法是一种以递归去遍历各种情况的搜索方式，搜索过程可抽象成遍历一棵N叉树的遍历过程，集合的大小构成树的宽度，递归的深度就构成了树的深度，遍历中会枚举所有情况，实际上就是一个暴力搜索的过程，有时候迭代遍历多层for循环做不出来的时候，可用回溯法做出来。

从大类来说可解决两大类问题，再细分下来是五小类问题：

• 组合性问题：
  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 分割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列性问题：
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

注：组合问题并不要求元素按一定顺序，排列问题要求元素按一定顺序。

参考文章：回溯法总结篇

（1）回溯法模板

解决一个回溯问题，实际上就是一个决策树的宾利过程，对于回溯树的一个结点，需要思考三个问题：
结束条件（到达决策树底层，无法再做选择的条件）；路径（已做出的选择）；选择列表（当前可做的选择）。

vector<bool> visitied;			// 排列问题时，使用visited判定是否访问过
vector<type> path;				// 存储某一条路径的情况
vector<vector<type>> res;		// 结果集
void backtracking(参数1, 参数2, ...) {
	if(终止条件) {
		存放结果;
		return ;
	}
	
	for (选择: 本层集合中元素(树中结点孩子的数量就是集合大小)) {
		处理结点;
		backtracing(路径, 选择列表);
		回溯，回退至处理结点之前的状况;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（2）去重方式

1. 有序数组去重：采用i > startIndex && nums[i] == nums[i - 1]
2. 无序数组去重：
   1. 不要求保留原序列顺序：无序变有序，再按有序方式去重；
   2. 要求保留原序列顺序：对于树层去重，每遍历到一层时，就新设置一个Hash表，用于记录是否访问过某一元素。

参考文章：回溯算法理论基础、回溯算法解题套路框架

2、组合问题

组合问题就是遍历一颗N叉树的过程，最终获取树中的所有叶节点。

一个集合求组合的话，需要用stratIndex来控制遍历起始下标。如果是多个集合取组合，各个集合间相互不影响，则不需要satatIndex。

（1）一个集合求组合

去重： startIndex用于选择路径，来保证是否去重结果集。当startIndex为i时，结果集中可含有相同的数；当startIndex为i+1时，结果集中不含有相同的数。

剪枝： 让数组按递增顺序排列，设置判定上界为n - (k - nums.size())，其中n为数组大小，单个k结果大小。上界以外的数，由于在之后遍历的时候一定会不符合单个结果要求个数，因此直接剪枝跳过。

1. 集合中元素不同，单个结果内元素仅能被选一次，结果间不重复
   114、【回溯算法】leetcode ——77. 组合：回溯法+剪枝优化（C++版本）：选择路径时，更新下标数为i + 1。
   115、【回溯算法】leetcode ——216.组合总和III：回溯法+剪枝优化（C++版本）：增加一个和是否为n的判定条件

2. 集合中元素有相同，单个结果内同一元素可被选多次，结果间不重复
   117、【回溯算法】leetcode ——39. 组合总和：回溯法+剪枝优化（C++版本） ：先按升序排列，选择路径时，更新下标数为i。

3. 集合中元素有相同，单个结果内各个元素仅能被选一次，结果间不重复
   118、【回溯算法】leetcode ——40. 组合总和 II：回溯法+剪枝优化（C++版本）：使用i > startIndex && nums[i] == nums[i - 1]来去重判定，选择路径时，更新下标为i + 1。

（2）多个集合取组合

1. 多个集合取组合一般性问题
   116、【回溯算法】leetcode ——17. 电话号码的字母组合：回溯法：哈希映射+字符串数组映射（C++版本）

3、切割问题

分割问题的整体过程与组合问题相似，都是依次选择某一元素再遍历，最终获取叶结点，不同之处在于分割问题在每次递归遍历前，要判定分割条件，当满足分割条件时，将元素进行分割，然后再递归的向下进行遍历。

119、【回溯算法】leetcode ——93. 复原 IP 地址（C++版本）：字符换成数字判定是否符合有效IP位

4、子集问题

如果把遍历过程看作遍历一颗树，那么子集问题就是收集树中所有的结点。而组合问题和分割问题则是获取树的所有叶节点。

1. 子集一般性问题
   123、【回溯算法】leetcode ——78. 子集（C++版本）

2. 子集去重
   122、【回溯算法】leetcode ——90. 子集 II：子集去重（C++版本）：有序数组

3. 递增序列
   123、【回溯算法】leetcode ——491. 递增子序列：unordered_set去重和int数组去重（C++版本）：保留序列原始顺序，获取递增子序列（相当于是找到符合某一条的子集），难点在于如何在无序数组中去重。

5、排列问题

排列问题的特点是区分元素顺序，即同一个元素占据不同的位置，会代表不一样的结果。而组合问题的特点是不区分元素顺序，即同一个元素，只要在这个结果中，无论占据那个位置都认为相同的。

1. 排列一般性问题
   124、【回溯算法】leetcode ——46. 全排列（C++版本）

2. 含重复数字需去重排序问题
   125、【回溯算法】leetcode ——47.全排列 II：visited去重（C++版本）：树层去重和树枝都可以，本题树层去重效率更高

6、棋盘问题

1. N皇后经典问题（二维信息判定）
   49、【图】N-皇后问题：二维信息判定（C/C++版）：按行遍历、设置列、副、主对角线记录

2. 解数独（三维信息判定）
   126、【回溯算法】leetcode ——37. 解数独：三维信息判定（C++版本）：判定行、列、3x3小单元内是否冲突，其中小单元判定的起始位置使用先除3再乘3的方式，保证从每个小单元起始位置遍历。