回溯：系列经典题目
前言
对于回溯算法，一开始接触感觉还是挺难的，随着刷到的题目的数量增多，慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码
public 返回值 backtrace(起始条件){
if(满足条件){
返回值;
}
for(所有可以的选择){
做出选择a;
backtrace(更新条件);
撤销选择a;
}
}当我们翻看我们所做过的所有回溯算法的相关题目时，其实可以发现使用的套路，都离不开上面的模板。
其实我们换一个思路来理解回溯算法，回溯说到底也就是一种穷举算法，尝试每一种可能，如果当前这种尝试计算到头都不符合最后的结果，那么我们就依次向后退步，再次尝试新的方案，并没有什么特别神秘的地方。
可是发现这个套路的同学应该也有很多，但是每次遇到回溯算法，依旧很难实现相关代码。其实主要原因在于我们有时候难以选取结束条件，还有就是不清楚我们到底有多少种选择。这才是大多数回溯算法困扰我们的地方。
下面我们一起来看3道比较经典的回溯算法题目，来找找感觉吧~
一、解数独
★LeetCode37 --- 解数独【困难】 ”
题目描述
如图所示：数独要求我们行、列以及九宫格内都不允许出现相同的数字，这样就可以构成一个数独了！
1.1 解题思路
题目会首先给我们一个不完整的9x9的数独，然后我们需要根据已有的信息，向里面添加数据，构成一个完整的数独。那么我们现在就按照上面的模板来完善这道题。
- 可以做出的选择：每个格子只能选择字符
1--9，而且只能对未填充的空格进行填写，所以我们首先可以确定自己的选择空间。 - 结束条件：在填写数独的每一个方格时，我们选择从左上角开始，从左到右，一行一行进行填写，直到最后一个方格，所以当我们填写到最后一个方格时，就可以代表之前填写的方格都是成功的，至此也就结束了我们整个解数独的过程。
- 每次更新的条件：通过结束条件我们可以看出，结束条件是依赖于填写的方格的位置的。由此我们可以推断出，每次的更新条件，也就是我们每次进行填写的方格的位置。
下面我们来实现一下我们的思路。
1.2 代码实现
public void solveSudoku(char[][] board) {
if(board == null || board.length != 9 || board[0].length != 9 ) return;//非法数独判断
back(board , 0 , 0);//进入回溯
}
private boolean back(char[][] board , int row , int col){
if(col == 9) return back(board , row+1 , 0);//处理边界情况，此时已经到达了最右边一列，进入下一行的迭代
if(row == 9) return true;//此时已经遍历完了board[8][8]，即已经全部遍历完了
if(board[row][col] != '.') return back(board , row , col+1);//当前字符不是空字符
for(char ch = '1' ; ch <= '9' ; ch++){
if(isValid(board , row , col , ch)){//查看当前字符如果放在此处是否合法
board[row][col] = ch;//如果合法，则此字符放置在此处
if(back(board,row,col+1)) return true;//进入递归，查看当前解是否为最终解
board[row][col] = '.';//如果不为最终解，则进行回溯
}
}
return false;
}
private boolean isValid(char[][] board , int row , int col , char ch){
for(int i = 0 ; i < 9 ; i++){
if(board[row][i] == ch) return false;//对当前行进行遍历，查看是否有重复元素
if(board[i][col] == ch) return false;//对当前列进行遍历，查看是否有重复元素
if(board[(row/3)*3 + i/3][(col/3)*3 + i%3] == ch) return false;//对当前方格进行遍历，查看是否有重复元素
}
return true;
}二、N皇后
★leetcode51---N皇后【困难】 ”
题目描述
2.1 解题思路
首先拿到这道题目，小白是有点懵逼的，不清楚什么是“皇后”之间的攻击，经过一番查阅之后，可以将皇后之间的攻击类比为下面这种情况：
N皇后攻击示意图
也就是说，一个“皇后”会以她自己为中心，进行散射性攻击，所有处于“皇后”对角线，行和列的位置都会被“攻击”，并且这种攻击是一直延续的，并不会受距离的限制。
说到这里，是不是也很类似于上面的解数独的题目。
我们依旧可以按照上面的套路来完成这道题，不过这道题和上一个有一个区别在于，每一个空格只有两种状态，选择或者不选择放置“皇后”。
此处我们按照行来进行遍历，对于“N皇后”问题，每一行都会放置一个“皇后”。所以我们在查询的时候，只需要判断当前位置的上半部分即可，下半部分为空，当前行也是只有一个“皇后”的。在每次的更新条件时，可以仅仅更新下一次回溯时“皇后”所在的行数即可。
2.2 代码实现
List<List<String>> res = new LinkedList<>();
public List<List<String>> solveNQueens(int n) {
if(n <= 0) return res;
char[][] board = new char[n][n];
for(int i = 0 ; i < n ; i++){
Arrays.fill(board[i],'.');
}
back(board , n , 0 );
return res;
}
private void back(char[][] board , int n , int row ){
if(row == n){//完成了一种解法，皇后的数量等于n
LinkedList<String> path = new LinkedList<>();
for(int i = 0 ; i < n ; i++){
StringBuilder sb = new StringBuilder();
for(int j = 0 ; j < n ; j++){
sb.append(board[i][j]);
}
path.add(sb.toString());
}
res.add(path);
return ;
}
for(int j = 0 ; j < n ; j++){
if(isValid(board , n , row , j)){//当前位置可以放置皇后
board[row][j] = 'Q';//做出选择
back(board , n , row+1);
board[row][j] = '.';//撤销选择
}
}
}
private boolean isValid(char[][] board , int n , int row , int col ){
for(int i = 0 ; i < row ; i++){//判断当前列是否已经有皇后
if(board[i][col] == 'Q') return false;
}
for(int left = col-1 , up = row-1 ; left >= 0 && up >= 0 ;left-- , up-- ){//判断左上
if(board[up][left] == 'Q') return false;
}
for(int right = col + 1 , up = row - 1 ; right < n && up >= 0 ; right++ , up--){//判断右上
if(board[up][right] == 'Q') return false;
}
return true;
}三、组合
★leetcode77----组合【中等】 ”
题目描述
3.1 解题思路
对于此题，我们依旧使用回溯算法来进行实现。我们需要从1---n中，选取k个数字，来完成组合，我们按照顺序来依次选择不同的数字进行组合。
- 每次的选择：我们每次选择的时候，应该将已经使用过的数据排除在外，每次的选择都是在剩余的数字中挑选。
- 结束条件：我们使用一个链表
path来保存每一次的选择数字，当链表的长度为k的时候，我们就完成了一次选择，所以结束条件应该以path的长度来判断。 - 每次的更新条件：为了避免重复选择，我们在每次更新条件时，应该限制可选数字的范围，避免重复选择，由于我们是按照顺序来选择每一次的数据，所以，在每次更新条件的时候，应该将下一次可选的第一个数字传输进去。
由此我们再次结束回溯的三个步骤，开始代码实现。
3.2 代码实现
List<List<Integer>> output = new LinkedList<>();//最后的结果
List<Integer> path = new LinkedList<>();//保存每一次的组合
public List<List<Integer>> combine(int n, int k) {
if(n < k || n <= 0 || k <= 0) return output;
backtrace(n , k , 1);
return output;
}
private void backtrace(int n , int k , int start){
if(path.size() == k){//当前组合是满足条件的
output.add(new LinkedList(path));
return;
}
for(int i = start ; i <= n ; i++){
path.add(i);//做出选择
backtrace(n , k , i+1);
path.remove(path.size() - 1);//撤销选择
}
}