写一下回溯算法,顺便用回溯算法解决这两道题: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,回溯算法入门篇就这样吧,明天继续肝回溯,光这些肯定还是不够的,冲!