在算法中，有一个很经典的算法：回溯法，其使用的搜索方法是深度优先搜索。

本文将介绍回溯法，手把手教大家学会如何写回溯法，以及在搜索过程中的剪枝函数，和一些注意事项。

🎈 作者：Eriktse
🎈 简介：19岁，211计算机在读，CCPC全国赛金牌，ICPC区域赛银牌退役选手🏆力争以通俗易懂的方式讲解编程和算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈欢迎加群一起玩耍~QQ群：600240150

回溯法

回溯法一般由递归实现，模板如下：

func()
{
    递归出口;

    剪枝函数;


    向后拓展(可能还包含剪枝)
    {

        修改现场;

        func();

        恢复现场;

    }
}

解决一切问题

用回溯法可以解决“几乎一切问题”，当然也只能在问题规模较小的时候使用，当问题规大于几百的时候基本就失效了（时间复杂度极高）。

生成解空间

回溯法可以用于生成解空间，其实就是一个“带剪枝的暴力枚举”。关于暴力枚举可以看这篇文章：《【C++算法基础】#2暴力枚举的方法论与优化技巧 – 大力出奇迹》。

回溯法通常用于生成“子集树、排列树”等解空间，然后再解空间中通过数学方法来“剪枝”，即减少一些不必要的操作，从而缩小解空间。最后找出最好的解。

往回走

回溯法之所以叫回溯，是因为所有子问题的解最终都要回归到根问题（暂且这么叫了，应该叫原问题？）。

同样也是通过“合并”的操作，利用函数关系进行解的传递。关于“搜索中的拆分与合并”欢迎看这篇文章：《【C++算法基础】#3分治法/二分法的本质理解 – 别找了，看这一篇融会贯通》

恢复现场

这是回溯法中及其关键的一步，常见的恢复现场包括对标记的恢复、数组状态的恢复、局面地图的恢复等等。

至此，你已经了解了回溯法的基本原理，可以尝试跟着写一下下面的例题。

N皇后问题

https://leetcode.cn/problems/n-queens/

N皇后问题是典型的回溯法问题，直接运用回溯法解决即可。

代码注释详细，可参考~

class Solution {
public:
    static const int N = 15;
    vector<vector<string>> res;
    vector<string> tmp;
    bitset<N> vis, vis2, vis3;//vis2标记主对角线，vis3标记副对角线

    void dfs(int dep, int n)//一层层拓展保证了每一行只有一个
    {
        if(dep == n)
        {
            res.push_back(tmp);
            return;//记得return！否则将会无限递归
        }

        //这里剪枝函数写在拓展过程中了

        for(int j = 0;j < n; ++ j)//向后拓展
        {
            int i = dep;
            if(vis[j] || vis2[i + j] || vis3[n - i + j])continue;//剪枝，这一列已经有点了，就不能再放到这里了，保证每一列只有一个

            vis[j] = true;//修改现场，打上标记，告诉下一层，这一列不能走了
            vis2[i + j] = true;
            vis3[n - i + j] = true;//给斜线打上标记，注意观察斜线的数学规律
            tmp[i][j] = 'Q';//标记为皇后

            dfs(i + 1, n);//注意！这里的dep + 1了。

            tmp[i][j] = '.';//恢复成点'.'
            vis3[n - i + j] = false;
            vis2[i + j] = false;
            vis[j] = false;//恢复现场
        }
    } 

    vector<vector<string>> solveNQueens(int n) 
    {
        tmp.resize(n);
        for(int i = 0;i < n; ++ i)
        {
            tmp[i].resize(n);
            for(int j = 0;j < tmp[i].size(); ++ j)tmp[i][j] = '.';//初始化为.
        }
        dfs(0, n);
        return res;
    }
};