回溯的核心思路
回溯算法是一种比较经典的算法思想。它的思想在于：通过枚举法，对所有可能的选择进行遍历。枚举的顺序一般是一条路走到黑，发现黑之后，回退一步，再向前尝试没有走过的路。直到所有的路都尝试过。因此，回溯法也可以理解为是走不通就退一步的枚举方式。
回溯的3个关键在于：
其中主要又用\(for\)循环和递归来实现。
- \(for\)循环的作用在于另寻他路，可以用\(for\)来实现选择所有的路径，例如我们走到了选择点\(a\)，向后的路有\(j\)条，那么我们就需要把这\(j\)条路径都选择一次才可以，使用\(for\)循环就是为了把所有向后的路径都尝试一遍；
- 递归实现的就是一条路走到黑和回退一步。一条路走到黑是指：递归每次向着\(for\)给出的路径向后继续走了一步。如果将递归放在\(for\)循环体内，每一次的循环，都会在给出一个路径后，继续沿着这个路径向后递归，直到走到递归的出口。
- 递归从出口出来之后，就会实现回退一步。从出口出来之后，这一层的\(for\)循环的其他选择就要开始执行，所以会继续执行当前节点的下一条可行路径，然后递归调用，就顺着这条没走过的路径又走了一步。
回溯算法的模板
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| def dfs():
if (回朔点）：
保存该结果
return
else:
for route in all_route_set : 逐步选择当前节点下的所有可能route
if 剪枝条件：
剪枝前的操作
return
else：
保存当前数据
self.dfs()
回朔清理
|
这里的剪枝是指,对于有些情况,再继续往后走也是没有用的,所以可以提前退出。
在这里梳理一下在leetcode上碰到的回溯算法的运用。
回溯算法理论基础
子集问题
子集问题一般是求一个N个数的集合里有多少符合条件的子集。而在树形结构中子集问题是要收集所有节点的结果
以下为leetcode上有关子集问题的两道题目：
子集
image-20211201195220013
分析这道题的话，就可以得到如下的树形递归结构，可以直到遍历这个树的时候，把所有节点记录下来，就是要求的子集集合。
78.子集
所以用Java代码表述就是：
以下使用\(idx\)来选择不同的路径
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
| class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
if(n == 0) {
ans.add(path);
return ans;
}
backtrack(nums, 0, n);
return ans;
}
private void backtrack(int[] nums, int idx, int end) {
ans.add(new LinkedList(path));
if(idx >= end) {
return ;
}
for(int i = idx; i < end; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, end);
path.removeLast();
}
}
}
|
子集
II
image-20211201200636381
90.子集II
这道题比起上一题，提到了可能包含重复元素，但是子集本身不能重复，即子集中可以允许有重复元素，但是子集不能重复。所以要考虑怎么在所有的子集中去重。
还是考虑上一题的递归树，对于同一个子集中的重复元素，他们是同一个路径下的重复元素，而对于不同子集，他们是同一个树层上的，所以应该想的是怎么去重同一个节点下后面的选择的去重。
于是考虑先将数组排序，这样相同节点就会在一起，如果当前节点和前面的元素相同，如果继续选择，就会产生相同的一条路径，会导致重复，所以如果和前面的元素相同了，应该考虑剪枝。
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
31
32
33
| class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
if(n == 0) {
ans.add(path);
return ans;
}
backtrack(nums, 0, n);
return ans;
}
private void backtrack(int[] nums, int idx, int end) {
ans.add(new ArrayList(path));
if (idx >= end) {
return ;
}
for(int i = idx; i < end; i++) {
if (i > idx && nums[i] == nums[i - 1]) {
continue;
}
path.add(nums[i]);
backtrack(nums, i + 1, end);
path.remove(path.size() - 1);
}
}
}
|
排列问题
排列问题的特殊在于同一个集合,如果顺序不一样,也是被视为不同的集合。所以对于每个排列问题，都需要从头开始，这样才能确保搜索了所有路径。
举个栗子：比如求\([1,2]\)的全排列，可以有\([1,2]\)和\([2,1]\)两种，同一个1出现在不同的位置就是不同的排列。
所以对于排列问题，我们不使用\(idx\)来标识当前位置，而使用一个\(used[]\)来标识是否使用过当前元素，因为使用过的元素，这个排列里肯定就不能再次使用。
46.
全排列
image-20211201214626759
46.全排列
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
| class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
int n = nums.length;
if (n == 0) {
return ans;
}
boolean[] used = new boolean[n];
backtrack(nums, used);
return ans;
}
private void backtrack(int[] nums, boolean[] used) {
if(path.size() == nums.length) {
ans.add(new ArrayList(path));
return ;
}
for(int i = 0; i < nums.length; i++) {
if(used[i]) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums, used);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
|
47.
全排列 II
image-20211201214720088
这道题比起上一题，数组里可能有重复数字，并且全排列不能重复。
这里的去重其实也是涉及了同一树层上的去重。
47.全排列II1
图中我们对同一树层，前一位（也就是nums[i-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
26
27
28
29
30
31
32
| class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
int n = nums.length;
if(n == 0) {
return ans;
}
Arrays.sort(nums);
boolean[] used = new boolean[n];
backtrack(nums, used);
return ans;
}
private void backtrack(int[] nums, boolean[] used) {
if(path.size() == nums.length) {
ans.add(new ArrayList(path));
return ;
}
for(int i = 0; i < nums.length; i++) {
if(used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
path.add(nums[i]);
used[i] = true;
backtrack(nums, used);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
|
组合问题
提供CDN加速/云存储服务
