写一下回溯算法，顺便用回溯算法解决这两道题：46. 全排列 、51. N 皇后
回溯算法概念
其实回溯算法其实就是我们常说的 DFS 算法，本质上就是一种暴力穷举算法。
解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
代码方面，下面是回溯算法的框架：
1
2
3
4
5
6
7
8
9
10
| result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
|
这样确实难以理解，下面我们先看看全排列这道题，我们可以一边看这道题一边结合上面的一些概念进行消化，效果更好！
全排列
我们在高中的时候就做过排列组合的数学题，我们也知道 n 个不重复的数，全排列共有 n! 个。
PS：为了简单清晰起见，我们这次讨论的全排列问题不包含重复的数字。
那么我们当时是怎么穷举全排列的呢？比方说给三个数 [1,2,3]，你肯定不会无规律地乱穷举，一般是这样：
先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……
其实这就是回溯算法，我们全都会的。
我们就称这棵树为决策树，因为我们求解问题就是围绕它进行的。
我们再贴出来上面回溯算法的框架：
1
2
3
4
5
6
7
8
9
10
| result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
|
接下来我们想一想我们是怎样解决这个问题的呢？
其实就是先遍历，也就是选择列表，对于这道题来说选择列表就是123，然后看是否满足条件，条件是什么？其实就是看123这三个数我们用完了没有。接着如果没有用完，那么就遍历123，首先要先判断，如果123已经有的数字前面已经使用，那么就要跳过这次，进行下一种情况。如果没有使用，那就把这次遍历到的数字添加，然后递归这个函数。递归完成之后，我们还需要把这次加入的数字删除掉，让它进行下一次递归。
其实，就是这样，主要的逻辑就是for循环中，记录结果情况，就是需要先进行判断满足结束条件那一段。
OK，这就是回溯，我们在代码的编写中，要往前看，看看是否符合情况。
好的，接下来，我们直接上代码了：
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
| List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
LinkedList<Integer> list = new LinkedList<Integer>();
backtrack(list,nums);
return res;
}
public void backtrack(LinkedList<Integer> list,int[] nums){
if(list.size()==nums.length){
res.add(new LinkedList(list));
return;
}
for(int i=0;i<nums.length;i++){
if(list.contains(nums[i]))
continue;
list.add(nums[i]);
backtrack(list,nums);
list.removeLast();
}
}
|
八皇后
上面的题目，如果我们能够将递归的逻辑弄明白之后，下面八皇后这道题大体上也是这样的逻辑。
我把题目截下来吧：
这道题，我们想自己想一想。
先定一行（或者一列）中皇后的位置，然后进行下一行皇后位置的确定，需要我们去判断是否符合情况。
就是这样一直循环，就可以了。
也是回溯的算法，我们还需思考一些小细节。
首先，结束条件是啥？就是遍历的行数（从0开始）等于n的时候。
做出选择其实就是那个位置的值为 ‘Q’。
撤销选择其实就是那个位置的值为 ‘.’。
对于主要的回溯函数：
1
2
3
4
5
6
|
public void backtrack(List<char[]> list,int row){
}
|
那么判断是否合法的函数的书写：
先判断列是否有皇后冲突。接着是对角线，分左上边和右上边。
这里直接写出来把：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
public boolean isValid(List<char[]> list,int row,int col){
int n = list.size();
for(int i = 0; i < n; i++) {
if(list.get(i)[col] == 'Q'){
return false;
}
}
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--,j++){
if(list.get(i)[j] == 'Q'){
return false;
}
}
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
if(list.get(i)[j] == 'Q'){
return false;
}
}
return true;
}
|
好的，有了这些我们去完成函数的编写，直接贴出来了：
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
| List<List<String>> res = new LinkedList<List<String>>();
public List<List<String>> solveNQueens(int n) {
List<char[]> list = new LinkedList<>();
for(int i=0;i<n;i++){
char[] chars = new char[n];
Arrays.fill(chars,'.');
list.add(chars);
}
backtrack(list,0);
return res;
}
public void backtrack(List<char[]> list,int row){
if(row==list.size()){
res.add(transform(list));
return;
}
int n = list.size();
for(int i=0;i<n;i++){
if(!isValid(list,row,i)) continue;
list.get(row)[i] = 'Q';
backtrack(list,row+1);
list.get(row)[i] = '.';
}
}
public List<String> transform(List<char[]> list){
List<String> ret = new LinkedList<>();
for(char[] chars:list){
ret.add(new String(chars));
}
return ret;
}
|
OK，回溯算法入门篇就这样吧，明天继续肝回溯，光这些肯定还是不够的，冲！