回溯算法作为一种经典的有效的暴力搜索策略。其基本思想是搜索过程中沿着一条路径一直往前走，当探索到某一步时发现无法满足要求时，则退回到上一步选择另外一条路径继续往前搜索。对于许多大规模复杂问题而言，很多时候都可以通过回溯算法尝试解决
算法模板
结合LeetCode刷题经验，现对回溯算法的解题思路进行总结，并形成下面的伪代码模板。我们首先需要两个全局变量：result、state。前者用于保存最终搜索结果；后者用于记录搜索过程中的状态信息。故在程序入口getResult方法中首先需要通过init方法完成全局变量的初始化，最后直接返回全局变量result作为题解即可。而这期间通过search方法进行回溯搜索即可
search方法的最重要思路是根据当前状态等信息获取下一步搜索的可选择空间，即通过调用getAvailableList方法实现，然后遍历该可选择空间。具体地对于每个选择，先判断是否符合条件。如果符合，则说明可以选择它继续往前搜索。那么我们第1步先做出选择，包括对状态变量state的更新；第2步通过递归调用search方法实现所谓的一直往前搜索；第3步当递归调用结束返回时则说明已经当前搜索路径已经退回到上一步了，这个时候我们就需要撤销第1步做出的选择对状态变量的影响了。总而言之，回溯的关键就在于在递归搜索之前需要做出选择，而在递归搜索之后需要撤销选择
前面提到search方法会一直递归调用下去。那递归终止条件是什么呢？其实也很简单，第一种是发现不满足合法条件时直接return，即所谓的剪枝优化；第二种则是搜索成功，此时需要根据状态等信息将当前的搜索结果添加最终结果当中去
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
public static class Solution {
private result;
private state;
public getResult(...) {
init(...);
search(...);
return result;
}
private void init(...) {
result = ...
state = ...
}
private void search(...) {
if( 不满足合法条件 ) {
return;
}
if( 满足搜索结束条件 ) {
...
return;
}
availableList = getAvailableList(...);
for(int[] tempIndex : availableList) {
if( 判断当前选择 是否满足 合法条件 ) {
...
search(...)
...
}
}
}
private getAvailableList(...) {
...
}
}
|
实践
LeetCode: 17. 电话号码的字母组合
这里以 LeetCode 第17题 <电话号码的字母组合> 为具体示例来进行阐述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。数字到字母的映射如下图（与电话按键相同），注意1不对应任何字母
示例 1：
输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,”b”,”c”]
按照模板则解法如下所示。由于本题在搜索过程中，任意一个搜索都是合法的，故不需要判断每次选择的合法性，直接按照 “做出选择-递归搜索下一个-撤销选择” 的思路进行处理即可
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
public static class Solution {
private static Map<Character, String> num2StringMap;
static {
num2StringMap = new HashMap<>();
num2StringMap.put('2', "abc");
num2StringMap.put('3', "def");
num2StringMap.put('4', "ghi");
num2StringMap.put('5', "jkl");
num2StringMap.put('6', "mno");
num2StringMap.put('7', "pqrs");
num2StringMap.put('8', "tuv");
num2StringMap.put('9', "wxyz");
}
private List<String> result;
private StringBuilder sb;
public List<String> letterCombinations(String digits) {
if( digits==null || digits.length()==0 ) {
return Collections.emptyList();
}
init();
search(digits, 0);
return result;
}
private void init() {
result = new LinkedList<>();
sb = new StringBuilder();
}
private void search(String digits, int index) {
if( index == digits.length() ) {
result.add( sb.toString() );
return;
}
char num = digits.charAt(index);
String choice = getChooseList(num);
for(char ch : choice.toCharArray() ) {
sb.append( ch );
search(digits, index+1);
sb.deleteCharAt( sb.length()-1 );
}
}
private String getChooseList(char ch) {
return num2StringMap.get(ch);
}
}
|
LeetCode: 51. N皇后
这里以 LeetCode 第51题 为具体示例来进行阐述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位
示例 1：
输入：n = 4
输出：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如下图所示，4皇后问题存在两个不同的解法
示例 2：
输入：n = 1
输出：[[“Q”]]
按照模板则解法如下所示。本题中对于皇后的放置位置有一定要求，棋盘中的行、列、斜线不同同时放置两个皇后，故在遍历时通过isValid方法保证当前选择的合法
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| public static class Solution {
private List<List<String>> result;
private Boolean[][] board;
public List<List<String>> solveNQueens(int n) {
init(n);
search(n, 0);
return result;
}
private void init(int n) {
result = new LinkedList<>();
board = new Boolean[n][n];
for(int i=0; i<n; i++) {
Arrays.fill( board[i], false );
}
}
private void search(int n, int rowIndex) {
if(rowIndex == n) {
convert();
return;
}
for(int colIndex=0; colIndex<n; colIndex++) {
if( isValid(rowIndex, colIndex) ) {
board[rowIndex][colIndex] = true;
search(n, rowIndex+1);
board[rowIndex][colIndex] = false;
}
}
}
private boolean isValid(int rowIndex, int colIndex) {
for(int i=0; i<board.length; i++) {
if( board[i][colIndex]) {
return false;
}
}
for(int i=1;;i++) {
int x1 = rowIndex - i;
int y1 = colIndex - i;
if( x1<0 || y1<0 ) {
break;
}
if( board[x1][y1] ) {
return false;
}
}
for(int i=1;; i++) {
int x1 = rowIndex - i;
int y1 = colIndex + i;
if( x1<0 || y1>board.length-1 ) {
break;
}
if( board[x1][y1] ) {
return false;
}
}
return true;
}
private void convert() {
List<String> tempList = new LinkedList<>();
for(int i=0; i<board.length; i++) {
String rowStr = Arrays.stream( board[i] )
.map( e -> {
if( e ) {
return "Q";
}
return ".";
} )
.collect(Collectors.joining());
tempList.add( rowStr );
}
result.add( tempList );
}
}
|
剑指Offer(第2版): 12. 矩阵中的路径
这里以 LeetCode 的剑指Offer(第2版)题单中的第12题 <矩阵中的路径> 为具体示例来进行阐述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
示例 1：
输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出：true
示例 2：
输入：board = [[“a”,”b”],[“c”,”d”]], word = “abcd”
输出：false
按照模板则解法如下所示。一方面本题每次的搜索路径为上、下、左、右这四个方向上未使用过的网络；另一方面本题只需判断能够搜索成功即可。所以当第一次搜索成功后，即可以不再进行搜索。故解法中加入了基于exist结果判断的剪枝优化
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
public static class Solution {
private int row;
private int col;
private boolean exist;
private boolean[][] usedArray;
public boolean exist(char[][] board, String word) {
if( board==null || board[0]==null || word==null || word==""
|| board.length*board[0].length < word.length() ) {
return false;
}
init(board, word);
search(board, word, 0, 0, 0);
return exist;
}
public void init(char[][] board, String word) {
exist = false;
row = board.length;
col = board[0].length;
usedArray = new boolean[row][col];
}
public void search(char[][] board, String word, int index, int i, int j) {
if( exist ) {
return;
} else if( index == word.length() ) {
exist = true;
return;
}
Set<int[]> indexSet = getAvailableIndexSet(index, i, j);
for(int[] tempIndex : indexSet) {
if(exist) {
break;
}
int rowIndex = tempIndex[0];
int colIndex = tempIndex[1];
if( board[rowIndex][colIndex] == word.charAt(index) ) {
usedArray[rowIndex][colIndex] = true;
search( board, word, index+1, rowIndex, colIndex);
usedArray[rowIndex][colIndex] = false;
}
}
}
public Set<int[]> getAvailableIndexSet(int index, int i, int j) {
Set<int[]> indexSet = new TreeSet<>( (a1, a2) -> {
if( a1[0] == a2[0] && a1[1] == a2[1] ) {
return 0;
}
return 1;
});
if( index == 0 ) {
for(int rowIndex=0; rowIndex<row; rowIndex++) {
for (int colIndex=0; colIndex<col; colIndex++ ) {
int[] tempIndex = new int[]{rowIndex, colIndex};
indexSet.add( tempIndex );
}
}
return indexSet;
}
int iMax = i+1 <= row-1 ? i+1 : row-1;
int iMin = i-1 >= 0 ? i-1 : 0;
int jMax = j+1 <= col-1 ? j+1 : col-1;
int jMin = j-1 >= 0 ? j-1 : 0;
indexSet.add( new int[]{iMin, j} );
indexSet.add( new int[]{iMax, j} );
indexSet.add( new int[]{i, jMin} );
indexSet.add( new int[]{i, jMax} );
indexSet.removeIf( tempIndex -> {
int rowIndex = tempIndex[0];
int colIndex = tempIndex[1];
return usedArray[rowIndex][colIndex];
} );
return indexSet;
}
}
|
剑指Offer(第2版): 13. 机器人的运动范围
这里以 LeetCode 的剑指Offer(第2版)题单中的第13题 <机器人的运动范围> 为具体示例来进行阐述
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
示例 1：
输入：m = 2, n = 3, k = 1
输出：3
示例 2：
输入：m = 3, n = 1, k = 0
输出：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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| class Solution {
private int result;
private boolean[][] usedFlag;
private int[] dx = new int[]{0,1};
private int[] dy = new int[]{1,0};
public int movingCount(int m, int n, int k) {
if( k<0 ) {
return 0;
}
init(m, n);
search(k, 0, 0);
return result;
}
private void init(int m, int n) {
usedFlag = new boolean[m][n];
usedFlag[0][0] = true;
result = 1;
}
private void search(int k, int rowIndex, int colIndex) {
for(int i=0; i<2; i++) {
int nextRowIndex = rowIndex + dx[i];
int nextColIndex = colIndex + dy[i];
if( nextRowIndex>=0 && nextRowIndex<=usedFlag.length-1
&& nextColIndex>=0 && nextColIndex<=usedFlag[0].length-1
&& calcSum(nextRowIndex, nextColIndex)<=k && !usedFlag[nextRowIndex][nextColIndex] ) {
result++;
usedFlag[nextRowIndex][nextColIndex] = true;
search(k, nextRowIndex, nextColIndex);
}
}
}
private int calcSum(int num1, int num2) {
int sum = 0;
while( num1!=0 ) {
sum += num1 % 10;
num1 = num1 / 10;
}
while( num2!=0 ) {
sum += num2 % 10;
num2 = num2 / 10;
}
return sum;
}
}
|
