回溯理论基础

回溯法(回溯搜索法),是一种搜索的方式。

只要有递归就会有回溯。

因此,回溯函数也就是递归函数,指的都是一个函数。

回溯的本质是穷举。

回溯法解决的问题

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

排列?组合?

组合是不强调元素顺序的,排列是强调元素顺序的。

组合无序,排列有序

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构。

因为回溯法解决的都是在集合中递归查找子集,集合的大小就构成了树的宽度,递归的深度都构成了树的深度。

回溯三部曲

  • 回溯函数模板返回值以及参数

名字:backtracking

返回值:一般为void

参数:一般先写逻辑,然后需要什么参数就填什么参数

  • 终止条件

一般来说搜到叶子节点也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归。

  • 回溯搜索的遍历过程

回溯法一般是在集合中递归搜索,集合的大小构成了树的宽度,递归的深度构成了树的深度

1
2
3
4
5
for(选择:本层集合中的元素(树种节点孩子的数量就是集合的大小)){
处理节点;
backtracking(路径,选择列表);//递归
回溯,撤销处理结果;
}

for循环可以理解为横向遍历,backtracking(递归)就是纵向遍历,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果了。

因此,回溯算法模板框架如下:

1
2
3
4
5
6
7
8
9
10
11
void backtracking(参数){
if(终止条件){
存放结果;
return;
}
for(选择:本层集合中元素(树种节点孩子的数量就是集合的大小)){
处理节点;
backtracking(路径,选择列表);//递归
回溯,撤销处理结果;
}
}

77.组合

文章:2. 组合问题

题目:77. 组合

把组合问题抽象为树形结构。每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围。不难发现,n相当于树的宽度,k相当于树的深度。接下来我们需要获取结果集,图中每次搜索到了叶子节点,我们就找到了一个结果。

回溯三部曲:

  • 递归函数的返回值以及参数

    定义两个全局变量,一个用来存放单一结果,一个用来存放符合条件结果的集合。

  • Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
List<List<Integer>> list = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n,k,1);
return list;
}
public void backtracking(int n,int k,int start){
if(path.size() == k){
list.add(new ArrayList<>(path));
return;
}
for(int i = start ;i <= n ; i++ ){
if(n-i+1 < k - path.size())break;
path.add(i);
backtracking(n,k,i+1);
path.removeLast();
}
}

}
  • Go实现

剪枝法:

1
2
3
if n-i+1 < k - len(tmp){
break
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func combine(n int, k int) [][]int {
res:=make([][]int,0)
tmp := make([]int,0)
//startIndex 每次回溯for循环用的初始索引
var backtracking func(n,k,startIndex int)
backtracking = func(n,k,startIndex int){
if len(tmp) == k{
temp := make([]int,k)
copy(temp,tmp)
res = append(res,temp)
return
}
for i:=startIndex;i<=n;i++{
if n-i+1 < k - len(tmp){
break
}
tmp = append(tmp,i)
backtracking(n,k,i+1)
tmp = tmp[:len(tmp)-1]
}
}
backtracking(n,k,1)
return res
}

【算法总结】

  • 组合:使用回溯+剪枝的方法,确定好每次遍历的初始索引,然后递归回溯回去添加即可。

【语言总结】

  • Java

    使用LinkedList来进行动态数组的添加,然后通过new ArrayList<>(list)转化为ArrayList的其中一个集合。