回溯算法

理论基础

回溯算法也叫做,回溯搜索法,它是一种搜索的方式

回溯的本质是穷举,穷举出所有的可能,再选出我们想要的答案

可以加一些剪枝的操作优化,但改变不了穷举的本质

回溯和递归是相辅相成的,递归函数的下面就是递归的过程

回溯算法解决的问题

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

组合问题:{1,2}{2,1}就是一个组合,不强调顺序

排列问题:{1,2}{2,1}就是两个组合,有顺序

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构,是的,我指的是所有回溯法的问题都可以抽象为树形结构!

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

递归就要有终止条件,所以必然是一棵高度有限的树(N叉树)。

这块可能初学者还不太理解,后面的回溯算法解决的所有题目中,我都会强调这一点并画图举相应的例子,现在有一个印象就行。

回溯算法理论基础

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}

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

77.组合

77.组合1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {
dfs(n, k, 1);
return ans;
}

public void dfs(int n, int k, int start) {
if (path.size() == k) {
ans.add(new ArrayList<>(path));
return;
}

for (int i = start; i <= n; i++) {
path.add(i);
//调用回溯函数,找下一个数字
dfs(n, k, i + 1);
//回溯的精华,将最后一个数字移除当前组合
path.remove(path.size() - 1);
//path.removeLast();
}
}
}

77.组合优化

77.组合4

简单来说就是,数的每一层是dfs(),每一层的个数是for循环控制的

当n=4,k=4的时候,[1-4]中所有可能只有一种,所以要在for循环中,排除不需要的分支

1.已经选择的元素是path.size();

2.所需要的元素是k-path.size();

3.剩余元素为n-(k-size)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();

public List<List<Integer>> combine(int n, int k) {
dfs(n, k, 1);
return ans;
}

public void dfs(int n, int k, int index) {
if (path.size() == k) {
ans.add(new ArrayList<>(path));
return;
}

for (int i = index; i <= n - (k - path.size()) + 1; i++) {
path.add(i);
dfs(n, k, i + 1);
path.removeLast();
}
}
}

216.组合优化III

在集合[1-9]中选取k个数,和n=4的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();

public List<List<Integer>> combinationSum3(int k, int n) {
dfs(k, n, 1, 0);
return ans;
}

public void dfs(int k, int n, int index, int sum) {
if (sum > n) {
return;
}
if (path.size() > k) {
return;
}
if (path.size() == k && sum == n) {
ans.add(new ArrayList<>(path));
return;
}
//在1-9中选择数字
for (int i = index; i <= 9; i++) {
path.add(i);
sum += i;
dfs(k, n, i + 1, sum);
sum -= i;
path.removeLast();
}
}
}