回溯算法，你“回”了吗

一、什么是回溯算法

二、应用场景

三、一般解题步骤

1、确定回溯方法以及参数

2、确定回溯的终止条件

3、确定搜索过程

四、力扣例题

1、题目描述

2、解题思路

3、代码示例

五、总结

一、什么是回溯算法

回溯算法，又称为试探法，是一种通过穷举所有可能情况来找到问题的解的方法。回溯算法通常采用深度优先搜索的策略，从一个选择开始，不断地向某一方向前进，直到无法继续。此时，需要回退到上一步选择的其他分支继续尝试，直到找到问题的解或无法继续搜索。

回溯算法的思想源于数学中的排列组合问题，通过尝试所有的可能性来找到问题的解。与穷举搜索相比，回溯算法具有剪枝操作，可以通过一些判断条件来减少搜索的路径，提高算法的效率。

回溯算法虽然能够解决很多问题，但是，他并不是一个高效的算法。因为回溯的本质其实就是穷举所有可能，然后从这个所有可能中根据条件筛选出我们想要的结果。这其实也就是暴力搜索。不过，有些时候也是非回溯算法不能解决。

二、应用场景

回溯算法适用于一些需要尝试所有可能解的问题，常见的应用场景有以下几种：

排列组合问题：对于一些需要找出所有排列组合的问题，如全排列、组合总和、电话号码的字母组合等，使用回溯算法可以轻松解决。需要注意的是，组合和排列的区别是，组合是不考虑顺序的，而排列是考虑顺序的。组合也就是只要选出的元素相同就是同一种情况。而排列虽然选出的元素相同只要顺序不同，那就是不同的情况。
子集问题：对于一些需要找出所有子集的问题，如子集求和、子集和为定值等，使用回溯算法可以事半功倍。
图遍历问题：对于一些需要遍历图的问题，如寻找路径、寻找最短路径等，使用回溯算法可以有效地解决。
棋盘问题：对于一些需要在棋盘上放置棋子的问题，如N皇后问题、数独等，使用回溯算法可以找出所有可能的解。

三、一般解题步骤

1、确定回溯方法以及参数

回溯方法一般命名backTracking，返回值一般为void，也就是不返回任何值。注意，这里说的是一般，具体需不需要返回值还需要根据具体场景来确定(比如，解数独的回溯方法就是需要有返回值的)。

而对于需要传的参数，一般是不能提前全部确定出来的。所以，我们可以先去实现这个回溯方法，然后在实现该方法的过程中，根据需要再去添加参数。

//大部分场景下回溯方法的返回类型都是void，所以这里就直接使用void
void backTracking(参数1，...,参数n)

2、确定回溯的终止条件

所有的回溯算法都是可以抽象为树形结构的。因为，回溯算法都是从一个集合中递归的查找子集。所以，该集合的大小就是树的高度，递归的深度也就是树的深度。既然，是递归那么就一定会有终止条件。因为递归的深度就是树的高度，所以当递归到树的叶子节点也就是找到了一条满足要求的结果。当然，我们也可以通过分析题目，来将一些明显不满足要求的给提前终止，避免造成不必要的搜索，这也就是剪枝。

if (终止条件) {
    //把得到的这条满足要求的结果放到结果集中
    ..........
    return;
}

3、确定搜索过程

回溯法一般抽象出的树形结构图如下：

回溯算法遍历的一般代码如下：

#index表示下次循环的起点，也就是确定下次递归的集合
for(int i=index;i<=n;i++){
 //对当前遍历出的节点进行处理
 ...............
 //调用回溯方法，构成递归
 backtrack();
 //进行回溯操作,退回节点处理前的状态
 .............
}

所以不难得出，回溯算法中的回溯方法的一般代码：

if (终止条件) {
    //把得到的这条满足要求的结果放到结果集中
    ..........
    return;
}
#index表示下次循环的起点，也就是确定下次递归的集合
for(int i=index;i<=n;i++){
 //对当前遍历出的节点进行处理
 ...............
 //调用回溯方法，构成递归
 backtrack();
 //进行回溯操作,退回节点处理前的状态
 .............
}

四、力扣例题

我们就拿力扣上面经典的回溯算法问题，51.N皇后来举例。

1、题目描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

1 <= n <= 9

2、解题思路

n*n的棋盘也就是一个n*n的二维数组。想要获取满足要求的结果，其实也就是需要不断试探，各种情况是否满足要求。这也就是回溯法。此时，for循环的是每一列，递归的是每一行。并且对于循环递归中已经不满足条件的，直接提前终止，避免不必要的搜索。该题抽象出来的树形结构图如下：

■ 确定回溯方法以及参数

backTracking(叶子节点的结果集, 行列大小n, 当前行);

■ 确定回溯的终止条件

从上面的树形图可以得知，当遍历到叶子节点或者已遍历的结果已经不能满足N皇后的要求后，便终止了。

   if (row == n) {
       res.add(arrayToList(resArray));
       return;
    }

 #这里提前进行判断了，不满足要求的就不会往下走了
 if (isValid(i, row, n, resArray)) {
     resArray[row][i] = 'Q';
     backTracking(resArray, n, row + 1);
     resArray[row][i] = '.';
  }

■ 确定搜索过程

从上面的树形图可以得知，递归的深度是由棋盘的行来控制，for循环是控制棋盘的列。这样每次for循环+递归调用回溯算法的时候也就确定了在棋盘中放置皇后的位置。

 // 每列进行判断，通过递归的row来控制行数
        for (int i = 0; i < n; i++) {
            // 验证当前行为row,列为i的元素是否满足要求，满足要求的话再进行后续操作
            if (isValid(i, row, n, resArray)) {
                resArray[row][i] = 'Q';
                backTracking(resArray, n, row + 1);
                resArray[row][i] = '.';
            }
        }

3、代码示例

class Solution {
    //最终返回结果
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        // 定义一个n行n列的二维数组来存储叶子节点的结果
        char[][] resArray = new char[n][n];
        // 初始化二维数组，默认都是'.'
        for (char[] c : resArray) {
            Arrays.fill(c, '.');
        }
        backTracking(resArray, n, 0);
        return res;
    }

    // 回溯方法
    public void backTracking(char[][] resArray, int n, int row) {
        // 终止条件
        // 这里为什么是用的row不是row+1,是因为回溯传过来的就是已经+1了
        if (row == n) {
            res.add(arrayToList(resArray));
            return;
        }
        // 每列进行判断，通过递归的row来控制行数
        for (int i = 0; i < n; i++) {
            // 验证当前行为row,列为i的元素是否满足要求，满足要求的话再进行后续操作
            if (isValid(i, row, n, resArray)) {
                resArray[row][i] = 'Q';
                backTracking(resArray, n, row + 1);
                resArray[row][i] = '.';
            }
        }
    }

    // 定义验证方法
    public boolean isValid(int col, int row, int n, char[][] resArray) {
        // 检查同一列
        for (int i = 0; i < row; i++) {
            if (resArray[i][col] == 'Q')
                return false;
        }
        //检查45度方向
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(resArray[i][j]=='Q')
             return false;
        }
         //检查135度方向
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(resArray[i][j]=='Q')
             return false;
        }
        return true;
    }

    // 定义将二维数组转换成list集合的方法
    public List<String> arrayToList(char[][] arrayChar) {
        List<String> list = new ArrayList<>();
        for (char[] c : arrayChar) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}