第七章回溯算法part4，解决排列问题、棋盘问题，还是要抽象出树形结构好解题。
491. 非递减子序列
1.1 解题分析
因为对给定的整数数组不能排序，所以相同的元素不一定相邻，本题需要用一个set集合来记录元素之前是否出现过，用以实现同一树层上的去重；同时，因为set集合仅表示同一树层的状态，不是全局路径级的，所以不需要回溯。
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 {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> findSubsequences(int[] nums) {
backtracking(nums, 0);
return result;
}
public void backtracking(int[] nums, int startIndex) {
if (path.size() >= 2) {
result.add(new ArrayList<>(path));
}
Set<Integer> used = new HashSet<>();
for (int i = startIndex; i < nums.length; i++) {
if (!path.isEmpty() && nums[i] < path.getLast()) continue;
if (used.contains(nums[i])) continue;
path.add(nums[i]);
used.add(nums[i]);
backtracking(nums, i + 1);
path.removeLast();
}
}
}
|
46. 全排列
2.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 {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
backtracking(nums, new boolean[nums.length]);
return result;
}
public void backtracking(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
path.add(nums[i]);
used[i] = true;
backtracking(nums, used);
path.removeLast();
used[i] = false;
}
}
}
|
47. 全排列 II
3.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
| class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
backtracking(nums, new boolean[nums.length]);
return result;
}
public void backtracking(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
path.add(nums[i]);
used[i] = true;
backtracking(nums, used);
used[i] = false;
path.removeLast();
}
}
}
|
51. N皇后
4.1 解题分析
之前说过，回溯搜索并不高效，其实就是通过递归来帮我们控制for循环嵌套的层数，对于一个4x4的棋盘，暴力搜索应该怎么做？4层for循环嵌套，每层去枚举该层的摆放位置对吧，回溯算法也是一样的。
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
private List<List<String>> result = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(chessboard[i], '.');
}
backtracking(chessboard, 0, n);
return result;
}
public void backtracking(char[][] chessboard, int row, int n) {
if (row == n) {
result.add(construct(chessboard));
return;
}
for (int i = 0; i < n; i++) {
if (!isValid(chessboard, row, i)) continue;
chessboard[row][i] = 'Q';
backtracking(chessboard, row + 1, n);
chessboard[row][i] = '.';
}
}
private boolean isValid(char[][] chessboard, int row, int col) {
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 'Q') return false;
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < chessboard.length; i--, j++) {
if (chessboard[i][j] == 'Q') return false;
}
return true;
}
private List<String> construct(char[][] board) {
List<String> res = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
res.add(new String(board[i]));
}
return res;
}
}
|
至此解决了棋盘问题的第一道题目，明确for循环的长度就是棋盘的宽度，递归的深度就是棋盘的高度，本题就能够抽象出树形结构，用回溯算法求解。
37. 解数独
5.1 解题分析
- 分析回溯算法三部曲：
- 参数和返回值是什么？ 返回值是boolean类型，找到一个可行的解就理解返回；参数就是输入的数独表。
- 确定递归的终止条件。 不需要终止条件，把表填满，就到达了叶子节点，就会返回true。
- 确定单层搜索的过程。 二层for循环确定数独表中的一个位置，对这个位置递归枚举数字1-9，如果都不合法返回false；有合法的则进入下一层递归，注意和回溯配合使用。
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
34
35
36
37
38
39
40
41
42
43
| class Solution {
public void solveSudoku(char[][] board) {
backtracking(board);
}
public boolean backtracking(char[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[i].length; j++) {
if (board[i][j] == '.') {
for (char k = '1'; k <= '9'; k++) {
if (isValid(board, i, j, k)) {
board[i][j] = k;
if (backtracking(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char k) {
for (int j = 0; j < board[row].length; j++) {
if (board[row][j] == k) return false;
}
for (int i = 0; i < board.length; i++) {
if (board[i][col] == k) return false;
}
int startRow = row / 3 * 3;
int startCol = col / 3 * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == k) return false;
}
}
return true;
}
}
|
6. 回溯算法总结
- 回溯总结篇
- 回溯是递归的副产品，只要有递归就会有回溯，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。