“回溯法”和“深度优先搜索”有什么区别？
“回溯法”（Backtracking）和“深度优先搜索”（Depth First Search-DFS），看起来名字截然不同，字面意思也没什么相似的，不过，如果你经常刷题，渐渐就不免会注意到这个问题。为什么这两者会凑到一起去了？
我最早注意到这个问题，是观看题解的示范代码，示范代码是一道使用“回溯法”解决的题目，可是很奇怪，函数却并命名为 dfs，明明是回溯法，怎么用 dfs 来命名函数呢？为啥不用 backtracking 命名函数呢？
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.
回溯法是一种通用的算法，用于找到一些计算问题所有的（或者部分的）解，尤其是约束满足类问题，该算法逐渐构建潜在的解，一旦确认潜在的解无法满足，则立刻抛弃。
回溯法一个最经典的例题是“八皇后”问题，在一个国际象棋棋盘上，尝试放 8 个皇后，这 8 个皇后不能互相攻击，尝试找到一种或所有的解。8 个皇后不能在在同一行，同一列，或者同一对角线上。
回溯法解题的步骤大概是，首先在第一行挑选一个位置防止一个皇后，然后在第二行，放置皇后的时候，就不能产生攻击，一旦发现第 8 个皇后已经放置完毕，则搜索到了一个解。如果还没有放足 8 个，就发现已经无处可以放置了，则返回上一行，将上一行的皇后换一个位置放置（回溯）。
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
深度优先搜索，是一种用于遍历或者搜索树或者图数据结构的算法。算法从树的根节点开始（或者图的任意节点），然后沿着连接节点的边，尽可能深的遍历图，直到回溯。
在深度优先遍历的定义里，出现了回溯这个词。不难想象，假设有一颗树，我们从根节点开始深度优先遍历，那么会从根节点，一直向下深入，直到叶子节点，这时候如果想继续遍历，则必须返回父节点，这样才能寻找兄弟节点进行遍历。这个“返回” 的过程，就根回溯极其类似。
结合维基百科的定义和两个算法的基本描述，我们不难发现这两个算法的相同之处，通俗点说，都是选定一种策略，一条路走到黑，如果走入死路，就退回来，重新选择。
这“两种”算法的另一个相同之处是，都是遍历解空间的一种策略，说直白点，都是“穷举”的算法，只不过，穷举解空间也好，穷举图也好，都需要选定一个策略，才能没有遗漏和没有重复的完成穷举。
所以，我自己更倾向于认为，这两者，其实是同一种算法，只是从不同角度出发去称呼他们。事实上，我打开了好几本中文版算法书，《算法 4》，《算法导论》之类的，《算法竞赛入门经典》《算法竞赛进阶指南》等等，几乎就没找到过关于“回溯法” 的介绍和定义。难怪那些搞竞赛的，遇到回溯法，都会用 dfs 去命名函数。
通过在 StackOverflow 搜索，还真有人问这个问题。
For me, the difference between backtracking and DFS is that backtracking handles an implicit tree and DFS deals with an explicit one. This seems trivial, but it means a lot. When the search space of a problem is visited by backtracking, the implicit tree gets traversed and pruned in the middle of it. Yet for DFS, the tree/graph it deals with is explicitly constructed and unacceptable cases have already been thrown, i.e. pruned, away before any search is done.
So, backtracking is DFS for implicit tree, while DFS is backtracking without pruning.
这个回答认为，回溯法，处理了隐式树，而 DFS 则处理显示的树。这看起来平凡，但是也意味深长。当使用回溯法遍历一个问题的搜索空间时，隐式树在遍历的过程中，进行剪枝。但是，DFS 算法则不同，显示的树或者图已经被构造出来了，那些不可达的节点，或者不可能的情况，此时已经被排除在外了，只要按部就班全部遍历即可。所以，他认为，回溯法就是隐式树/图的深度优先搜索，而 DFS 就是没有剪枝的回溯法。
当然，也有很多回答认为是两种不同的算法，只是我比较倾向于这个答案。也有从字面去解释的，我觉得也可以听听，比如有人说，回溯法是解决问题的方法论，而 DFS 是算法。隐式图，显示图什么的，也不那么难以理解。事实上，我认为现实世界里，只有隐式图，真正的显示图是很罕见的。正因为我们对现实世界进行了抽象，才出现了显示图这种东西。
比如，使用回溯法常见的一类问题就是排列组合问题。例如经典的，使用 n 对括号，能排列出多少种合法的括号串（括号必须配对）。这是经典的需要回溯法解决的问题，你能把这个问题想象成图么？不管如何，如果你能把这个问题写成一个递归函数来解决，至少在递归深入到下一层和回来的过程，都绘制成节点和边的话，这个可视化出来的东西，就是一棵树（树是图的特例）。
所以，不用在纠结“深度优先搜索”和“回溯法”有什么区别了，只要知道，这两者就是一体两面，或者你认为根本是一回事也不为过。显示图和隐式图也没任何区别。只是隐式图更贴近显示世界，而显示图更贴近抽象世界。如此而已。