回溯算法解题总结
回溯算法解题总结
一、什么是回溯？
回溯算法实际上就是一个类似于枚举的搜索尝试过程，主要就是在搜索尝试的过程中寻找问题的解，当
发现已不满足求解条件的时候，就“回溯”返回，尝试别的路径。
用一句通俗的话来说就是：从一条路向前走，能进则进，不能进则退回来，换一条路再走
二、解决回溯问题的通用模板
解决一个回溯问题，实际上就是一个决策树的遍历过程，主要思考三个关键点
路径：也就是已经做出的选择
选择列表：也就是当前可以做的选择
结束条件：也就是到达决策树的底层，无法再做选择的条件
回溯算法的整体框架
result = []
def backtrack(路径,选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径，选择列表)
撤销选择
#for循环的细节如下
for 选择 in 选择列表:
//做选择
将该选择从选择列表中移除
路径.add(选择)
backtrack(路径，选择列表)
//撤销选择
路径.remove(选择)
将该选择再加入选择列表
其核心就是for循环里面的递归，在递归调用之前做选择，在递归调用之后撤销选择；这种递归前的选择和
递归调用后的选择其实与树的前序遍历和后续遍历非常相似，而所谓的前序遍历和后续遍历可以理解为两个有
用的时间点而已，前序遍历的代码在进入某一个节点之前的那个时间点进行，后续遍历代码在离开某个节点之
后的那个时间节点执行。遍历和选择的示意图可以参考如下：
回溯算法的时间复杂度是O(N!) ，因为穷举整颗决策树是无法避免的，不像动态规划存在重叠子问题
回溯算法就是纯暴力穷举，复杂度一般都比较高
三、典型例题（全排列和N皇后）
1.Leetcode 46 全排列
以全排列问题来示例回溯框架算法的使用
class Solution {
private List<List<Integer>> res = new LinkedList<>(); //二维列表
//主函数，输入一组不重复的数字，返回它们的全排列
public List<List<Integer>> permute(int[] nums) {
LinkedList<Integer> track = new LinkedList<>(); //记录走过的路径
backtrack(nums,track);
return res;
}
//路径：记录在track中
//选择列表：nums 中不存在于track的那些元素
//结束条件：nums中的元素全都在track中出现
public void backtrack(int[] nums,LinkedList<Integer> track){
if(track.size() == nums.length){ //当前路径长度和数组长度相同
res.add(new LinkedList(track)); //将当前路径当作一种可能的结果添加到结果中去
return;
}
for(int i = 0;i < nums.length;i++){
if(track.contains(nums[i])) continue; //如果当前元素已出现，结束当前循环
track.add(nums[i]); //做选择
backtrack(nums,track); //继续
track.removeLast(); //撤销选择
}
}
}
对于全排列问题，还有升级版的，就是当数组中含有重复数字时，返回不重复的排列，这里问题我们只要
增加剪枝的条件的即可处理
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort() #先对数组进行排序，不会走两条相同的路径
self.res = [] #存放最终返回的结果
self.backtrack(nums,[])
return self.res
def backtrack(self,nums,path): #nums是选择列表，path是路径
if nums == []: #遇到终止条件时将当前路径加入结果集
self.res.append(path)
return
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]: #剪枝，避免走重复的路径
continue #每当进入一个新的元素时先判断是否和上个元素一样
self.backtrack(nums[:i] + nums[i+1:],path + [nums[i]]) #避免重复利用当前元素，所以无需撤销
2.Leetcode 51 N皇后
class Solution {
private List<List<String>> res = new ArrayList<>(); //创建最终的返回列表
public List<List<String>> solveNQueens(int n) {
int[][] board = new int[n][n]; //二维数组，数组中有皇后用1标记，无皇后用0标记
backtrack(n,0,board); //回溯
return res;
}
public void backtrack(int n,int row,int[][] board){
if(row == n){ //全部行数都已经遍历完
res.add(track(board,n)); //将当前结果加入到最终列表中
return;
}
for(int col = 0;col < n;col++){
if(isUsable(board,row,col)){ //判断当前位置是否能放置皇后
//做出选择
board[row][col] = 1; //放置皇后
//填写下一行
backtrack(n,row+1,board);
//撤销
board[row][col] = 0; //撤销当前选择
}
}
}
//将每一个输出的结果转换成标准的格式输出
public List<String> track(int[][] board,int n){
List<String> list = new ArrayList<>();
for(int i = 0;i < n;i++){
StringBuilder str = new StringBuilder(); //可变对象
for(int j = 0;j < n;j++){
if(board[i][j] == 0) str.append('.');
else str.append('Q');
}
list.add(str.toString()); //列表中的每一个元素都是一个字符串
}
return list;
}
public boolean isUsable(int[][] board,int row,int col){
//检查同一列上有无皇后
for(int i = 0;i < row;i++){
if(board[i][col] == 1) return false;
}
//检查左上方是否有N皇后
int n = board[0].length;
for(int i = row - 1,j = col - 1;i >= 0 && j >= 0;i--,j--){
if(board[i][j] == 1) return false;
}
//检查右上方是否有N皇后
for(int i = row - 1,j = col + 1;i >= 0 && j < n;i--,j++){
if(board[i][j] == 1) return false;
}
return true;
}
}
四、回溯总结
回溯算法本质上可以看成多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置上做了不同的操作
写backtrack函数时，需要维护走过的路径和当前可以做的选择列表，当触发结束条件的时候，将路径记录
进结果集中就可以。主要的算法框架如下：
def backtrack(...):
for 选择 in 选择列表：
做选择
backtrack(...)
撤销选择
五、回溯和动态规划的联系
回溯算法和动态规划是非常相似的，动态规划需要明确的三个点就是状态、选择和base case，这三
个元素就对应着回溯算法中走过的路径、当前的选择列表和结束条件
从某种程度上说，动态规划的暴力求解阶段就是回溯算法，只是有的问题具有重叠子问题的性质，可
以使用dp table或者备忘录进行优化，将递归树大幅度的剪枝。而对于回溯的问题，没有重叠的子问题了，
复杂度非常高是不可避免的