回溯算法小笔记
回溯其实就是递归，只不过是递归的副产品，但递归不一定是回溯
回溯法其实就是暴力搜索的一种形式，不是什么很高级的算法，只不过有些题目能暴力搜出来就不错了，只能使用递归，最多再额外进行一些减枝操作。
回溯主要解决的问题有如下几种：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 棋盘问题：N皇后，解数独等等
理解回溯法时候，可以把回溯法跟树形结构联想起来，回溯法一定可以抽象为树形结构。
关键词：回溯、暴力、递归、解决特定问题、树形结构
回溯法模板
这里给出Carl总结的回溯算法模板。
在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。
回溯算法中函数返回值一般为void。
再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
但后面的回溯题目的讲解中，为了方便大家理解，我在一开始就帮大家把参数确定下来。
回溯函数伪代码如下：
既然是树形结构，那么就知道遍历树形结构一定要有终止条件。
所以回溯也有要终止条件。
什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
所以回溯函数终止条件伪代码如下：
if (终止条件) {
存放结果;
return;
}
|
在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
如图：
注意图中，我特意举例集合大小和孩子的数量是相等的！
回溯函数遍历过程伪代码如下：
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
|
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
分析完过程，回溯算法模板框架如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
|
这份模板很重要，后面做回溯法的题目都靠它了！
具体典型案例
组合问题
216.组合问题3
力扣题目链接(opens new window)
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
实现代码：
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
int temp =0;
public List<List<Integer>> combinationSum3(int k, int n) {
backTrack(n,k,1);
return result;
}
public void backTrack(int n,int k,int index){
if(path.size() ==k){
if (temp == n) {
result.add(new ArrayList<Integer>(path));
return;
}
return ;
}
if(temp > n) return;
for(int i=index;i<=9-k+path.size()+1;i++){
path.add(i);
temp += i;
backTrack(n,k,i+1);
temp -= path.get(path.size()-1);
path.remove(path.size()-1);
}
}
}
|
切割问题
131.分割回文串
力扣题目链接(opens new window)
给定一个字符串 s，
将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: “aab” 输出: [ [“aa”,”b”], [“a”,”a”,”b”] ]
实现思路：
这道题算是和medium到hard的一道，其实并不简单。但核心思路和前面的组合差距不大，可以以相似的思路：
例如对于字符串abcdef：
- 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…..。
- 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…..。
同理， 这样的分割问题也可以抽象为一颗树，
但我自己第一次在做的时候还是卡了很久的，思路没转过来，说明没彻底融会贯通回溯的思想。
实现代码:
class Solution {
List<List<String>> result = new ArrayList<>();
List<String> save = new ArrayList<>();
public List<List<String>> partition(String s) {
backTrack(s,0);
return result;
}
public void backTrack(String str,int index){
if(index == str.length()){
result.add(new ArrayList<>(save));
return;
}
for(int i=index+1;i<=str.length();i++){
String temp = str.substring(index,i);
if(ifRestr(temp)){
save.add(temp);
backTrack(str,i);
}
else continue;
save.remove(save.size()-1);
}
}
public boolean ifRestr(String str){
int n = str.length()-1;
for(int i=0;i<n;i++){
if(str.charAt(i) != str.charAt(n)) return false;
n--;
}
return true;
}
}
|
子集问题
90.子集II
力扣题目链接(opens new window)
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
求子集问题和前面两个又不一样了，如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
subsetGet(nums,0);
return result;
}
public void subsetGet(int[] nums,int index){
result.add(new ArrayList<>(path));
if(index >= nums.length) return;
for(int i=index;i<nums.length;i++){
path.add(nums[i]);
subsetGet(nums,i+1);
int temp = path.get(path.size()-1);
while((i+1)<nums.length &&nums[i+1]==temp){
i++;
}
path.removeLast();
}
}
}
|
排列问题
47.全排列 II
力扣题目链接(opens new window)
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
- 输入：nums = [1,1,2]
- 输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：
- 输入：nums = [1,2,3]
- 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10
解题代码：
```
#### n皇后问题
先记录一下自己很丑陋的耗时90mins写出来的笨蛋方法：
```java
class Solution {
List<List<String>> result = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chess = new char[n][n];
for(char[] raw:chess){
Arrays.fill(raw,'.');
}
nQueen(n,chess,0);
return result;
}
public void nQueen(int n,char[][] chess,int index){
if(index ==n){
result.add(Arrays.stream(chess).map(String::new).collect(Collectors.toList()));
return;
}
for(int i=0;i<n;i++){
if(ifLegal(n,chess,index,i)) chess[index][i] = 'Q';
else continue;
nQueen(n,chess,index+1);
chess[index][i]='.';
}
}
public boolean ifLegal(int n,char[][] chess,int r,int l){
for(int i=0;i<n;i++){
if(chess[i][l] == 'Q') return false;
}
for(int j=0;j<n;j++){
if(chess[r][j]=='Q') return false;
}
int i = Math.min(r,l);
while(r-i<n&&l-i<n){
if(chess[r-i][l-i]=='Q') return false;
i--;
}
int j=Math.min(n-r-1,l);
while(r+j>=0&&l-j<n){
if(chess[r+j][l-j]=='Q') return false;
j--;
}
return true;
}
}
|
较优的题解：
