最近面试刷题倒是刷出心得了，两年前疯狂的刷了一次题目搞懂了动态规划，当时对于回溯特别困惑。然后这一次刷题不知不觉吃透了整个回溯加剪枝。对于利用动态规划方式来剪枝叶，实际上动态规划剪枝是空间换时间的一种方式。
1. 回溯
78. 子集
我觉得Leetcode78这题是特别典型的回溯，就好比跳台阶是动态规划的入门一样。典型的原因就是因为这一题就是纯粹的回溯递归，不需要任何判断来过滤一些无用的数据。
这一题的一个特点就是元素互不相同，这和我们后面另外一题子集有所区别。我们先来看看编码，如下：
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>(); //用于收集返回的结果集
collectData(nums, result, new ArrayList<>(), 0); //调用递归方法，初始的index是0
return result;
}
//path是用来存储子集的，且在回溯的过程中会发生改变
// startIndex用来控制是否复用集合中的数据，下文会专门讲讲
private void collectData(int[] nums, List<List<Integer>> result, List<Integer> path, int startIndex){
//一般此处会有条件判断来决定结束递归，但是根据题意直接收集数据，因为path会变动，所以要深拷贝
result.add(new ArrayList<>(path));
for(int index = startIndex; index < nums.length; index ++){
//添加数据到子集中
path.add(nums[index]);
collectData(nums, result, path, index + 1); //递归调用，index + 1表示对于提供数组数据不重用
//回溯回退，需要剔除加入的当前值
path.remove(path.size() - 1);
}
}
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
初学者学习递归是对于其调用过程可能不是很理解，我通过一张图来阐述子集那一题的调用过程(ps:这个图画的好辛苦)
可视化整个调用过程后，执行完remove逻辑后发现了一个规律：
- startIndex = 0 => path = [] size始终是0
- startIndex = 1 => path = [1] size始终是1
- startIndex = 2 => path = [1, 2]/[2, 3] size始终是2
上述通过循环的方式来实现递归的，还有一种是只有两种选择，比如左右括号或者二叉树这种，这也需要递归，但是就用不到循环了。
22. 括号生成
这一题在递归过程完全是通过左右括号来递归的，我们来看看编码，如下：
/**
完成此题要保证两点：
1. 括号组合的长度固定是 2 * n，这也是结束递归的条件
2. 在任何时刻：
+ ( 的数量不能超过 n
+ ) 的数量不能超过 (，否则就是非法括号序列
*/
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
collectData(result, 0, 0, n, "");
return result;
}
/**
* result 用于收集数据；
* leftIndex表示左括号的数量；
* rightIndex表示右括号的数量；
* n是题目的参数，整个递归过程都要用；
* path是用于收集左右括号的；
*/
private void collectData(List<String> result, int leftIndex, int rightIndex, int n, String path){
//递归结束的条件
if(path.length() == 2 * n){
result.add(path);
return;
}
//这里保证左括号的数量不能超出题目所给的数
if(leftIndex < n){
collectData(result, leftIndex + 1, rightIndex, n, path + "("); //当使用了左括号添加时，那么左括号的值就要对应加1 然后path要加上左括号
}
//右括号的数量不能多于左括号，否则就是不合法的了
if(leftIndex > rightIndex){
collectData(result, leftIndex, rightIndex + 1, n, path + ")");
}
}
Note: 对于括号生成过程，我们是可以通过枚举的方式，因为不是左括号就是有括号。但是对于子集这题，提供的数组是可变的，我们必修依赖for循环的方式来完成递归。
回顾一下我在做括号这题：当时的path我用的是StringBuilder而不是String类型，我当时还很开心，感觉可以提升性能，然后运行发现面临一个问题就是回溯的时候我怎么把StringBuilder中的括号给去掉，懵逼了。
因为在做第一题子集的时候形成了一种思维定势，对于list我们可以将最后一个元素remove进行回溯，但是StringBuilder不行啊(后来看了一下有对应deleteCharAt这样的方法)。一看答案恍然大悟，String的不可变特性就保证了path在某一层递归中不会改变，所以对于添加右括号的时候不需要对于之前的值进行回退。
上述两种是对于for循环和根据不同条件来枚举进行递归调用，那么对于一些回溯需要记录对应的使用状态，看一下下面这题。
46. 全排列
这题和子集的不同点是全排列中的集合的子集合元素数量和数组的长度保持一致，另外一点不可以存在重复的元素，顺序不关心。也就是[1, 2, 3]和[1, 3, 2]是两个不同的。
/**
* 既然是去排列，我们要枚举出所有类型，因此也会存在[1, 1, 1]，[2, 2, 2]这种，但这两种是不符合题意的，
* 因为元素重复了，所以我们就要想办法怎么去除重复的元素
* 于是我们可以通过一个boolean数组来记录该元素是否使用过
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
//用于记录元素是否使用的数组
boolean[] used = new boolean[nums.length];
collectData(nums, result, new ArrayList<Integer>(), used);
return result;
}
/**
* nums是题目提供的数组
* result是用于收集结果集
* path是用于结果集的子集
* used是用于记录数据是否被使用过
*/
private void collectData(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] used){
//和子集那一题的区别是这里有对应的结束递归条件
if(path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
//此处没有startIndex，每次都是从0开始的，所以会存在[1, 1, 1]和[2, 2, 2]这种重复元素的情况，我后面会对各种情况进行总结
for(int index = 0; index < nums.length; index ++){
//对于使用过的元素进行状态判断，构建合法集合
if(used[index]){
continue;
}
used[index] = true; //使用了就记录状态；
path.add(nums[index]);
collectData(nums, result, path, used);
used[index] = false; //回溯后就恢复之前的状态；
path.remove(path.size() - 1);
}
}
77. 组合
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
collectData(n, k, result, new ArrayList<Integer>(), 1);
return result;
}
private void collectData(int n, int k, List<List<Integer>> result, List<Integer> path, int startIndex){
if(path.size() == k){
List<Integer> tempList = new ArrayList<>();
for(Integer value : path){
tempList.add(value);
}
result.add(tempList);
return;
}
for(int index = startIndex; index <= n; index ++){
path.add(index);
collectData(n, k, result, path, index + 1); //index + 1 是为了防止出现 1,1 2,2 3,3这种情况
//不满足需要退出path中最后一条数据
path.remove(path.size() - 1);
}
}
总结一下，对于回溯递归场景重视四点：
- 结束递归的条件；
- 选在for循环还是根据条件枚举递归；
- 如果需要记录状态，需要在递归过程根据状态进行递归；
- startIndex的选择问题；
startIndex的选择分析：
在子集和组合这两题中index在递归时都是加1的，但是对于全排列是没有出现startIndex，实际上就是当作0来处理的，以组合这一题为例子:
输入：n = 4, k = 2
startIndex = 1 => [[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,4],[3,1],[3,2],[3,3],[3,4],[4,1],[4,2],[4,3],[4,4]]
startIndex = index => [[1,1],[1,2],[1,3],[1,4],[2,2],[2,3],[2,4],[3,3],[3,4],[4,4]]
startIndex = index + 1 => [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
我想根据结果很好理解这三者之间的区别：
startIndex = 1 每一层的递归都是新的，没有任何依赖，index都是从1开始；
startIndex = index 每一层的递归存在依赖，但是会包括自身；
startIndex = index + 1每一层的递归存在依赖，但是会不包括自身；
如何理解自身：例如[1, 1], [2, 2]这样的结果就是包含自身的，对于[1, 2], [2, 3]这种直接去取下一个index的值，不包含自身的值；
回溯模版总结
void backtrack(参数...) {
if (终止条件) {
收集结果;
return;
}
for (选择 : 当前层的所有可选项) {
if (剪枝条件) continue;
做出选择;
进入下一层递归 backtrack(...);
撤销选择（回溯）;
}
}
2. 回溯 + 剪枝
在第1部分的全排列中已经提过根据状态判断来进行递归，实际上剪枝就是根据条件进行过滤，减少重复的递归。我一开始以为根据状态过滤就是剪枝，后来和ChatGPT交流了一下，得出如下的结论：
- 状态判断是手段，剪枝是目的;
- 如果状态判断只是为了构造合法路径 ➜ 不是剪枝；
- 如果它能提前阻止无效路径搜索 ➜ 才是剪枝;
需要剪枝的场景就是出现重复元素:
90. 子集 II
因为出现重复的元素，如何在递归的过程去除重复的元素递归是一个问题，也就是这个枝干我们怎么去剪。一个比较科学的方式：
- 将所有元素进行排序；
- 在递归过程如果发现下一个和上一个的元素一样就要剪枝；
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
//先排序是为了去重
Arrays.sort(nums);
collectData(nums, result, new ArrayList<>(), 0);
return result;
}
public void collectData(int[] nums, List<List<Integer>> result, List<Integer> path, int startIndex){
//和子集一样，上来就要对集合添加到结果集
result.add(new ArrayList<>(path));
for(int index = startIndex; index < nums.length; index ++){
//唯一的不同是这里，当出现前后相同时就要剪枝
if(index > startIndex && nums[index] == nums[index - 1]){
continue;
}
path.add(nums[index]);
collectData(nums, result, path, index + 1); //加1的目的是每个数字在内部List中只会使用一次
path.remove(path.size() - 1);
}
}
讨论一下剪枝条件：
index > startIndex && nums[index] == nums[index - 1]
其实我当时想到了后者条件，对于相同的需要跳过，然后发现索引溢出了，然后很自然的变成了如下条件：
index > 1 && nums[index] == nums[index - 1]
发现对于题目输入：[1,2,2] 输出的是：[[],[1],[1,2],[2]]。预期的是：[[],[1],[1,2],[1,2,2],[2],[2,2]]
index > startIndex的回溯过程:
startIndex=0: []
├── index=0: [1] → startIndex=1
│ ├── index=1: [1,2] → startIndex=2
│ │ ├── index=2: [1,2,2]
│
├── index=1: [2] → startIndex=2
│ ├── index=2: [2,2]
│
├── index=2: ← 这里如果没有剪枝，[2] 会再次被尝试
//这里剪枝只出现在startIndex = 0中，index = 2的情况
index > 1 的回溯过程:
startIndex=0: []
├── index=0: [1] → startIndex=1
│ ├── index=1: [1,2] → startIndex=2
│ // index=2: [1,2,2] 这里会满足index>1的条件导致无法输出[1,2,2]
│
├── index=1: [2] → startIndex=2
│ // index=2: [2,2] 这里会满足index>1的条件导致无法输出[2,2]
│
├── index=2: ← 这里如果没有剪枝，[2] 会再次被尝试
//这里剪枝出现在startIndex = 0，index = 2; startIndex = 1，index = 2; startIndex = 2，index = 2 三种情况
两者的区别：
index > startIndex是对于同一层递归中进行剪枝；（如果不理解层的概念，看一下我上面画的图）
index > 1是对于所有层的递归中进行剪枝；
47. 全排列 II
这一题也是出现重复的数据。
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
//和上面那题一样，出现重复的就是要排序的
Arrays.sort(nums);
collectData(nums, result, new ArrayList<Integer>(), used);
return result;
}
private void collectData(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] used){
//结束递归条件
if(path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
}
//全排列的话index就要从0开始， 主要是为了去重复数字
for(int index = 0; index < nums.length; index ++){
if(used[index]){
continue;
}
//确保同一层中，前后相等，并且前面的没有使用，因为前面使用了，会导致在后面再使用产生重复
// **剪枝去重关键逻辑**
if(index > 0 && nums[index] == nums[index - 1] && !used[index - 1]){
continue;
}
used[index] = true;
path.add(nums[index]);
collectData(nums, result, path, used);
used[index] = false;
path.remove(path.size() - 1);
}
}
按照上述的理论挑战middle难度的回溯基本是没有问题的，如果加大难度试试N皇后吧，少年！！！