：学懂回溯法

回溯法，是算法面试和竞赛里面，最常使用的一种算法“套路”。实质上是一种“隐式图”的搜索算法，也有人说，就是一种类型的“深度优先搜索”（DFS），也是一种“递归”的典型应用，一种“枚举”法，也可以说是“暴力搜索”法。
我在 LeetCode 刷题的时候，遇到很多题目，被打上了“回溯法”的标签，然而还是不会做，真要写还是完全写不出来。于是，就下决心我一定要学会回溯法。至少，再看到类似的题目，不会感到畏惧。
要说回溯法的最经典题目，就是“八皇后”问题了，意思就是在国际象棋的棋盘上，放上八个皇后，这八个皇后，互相不能攻击，求出一种解法，或者求出所有解法，或者求出解的数量，都是这道题目的经典问法，也有扩展到“N皇后”问题。相信有所了解的读者一定不会陌生这题。（皇后，是国际象棋里，子力最强的一枚棋子，对横行，竖列，斜对角线，都会产生攻击）
这样的问题，我们是不能凭着自己的感觉，直接说出哪怕是一种答案的，更别提给出所有的答案。所以，需要使用算法来找出答案。最直观的想法，就是把皇后一个一个放到棋盘上，如果产生了攻击，就换一个位置放，直到所有 8 个皇后都摆放上去，就找到了一个正确的答案。
这样的 try and error 的方式，正是回溯法的思路。我想，这个思路如果静下心来，一点都不难理解，难点是怎么用代码把它写出来。如果掌握了这一点，所有类似的题目，就都可以解决了。