DFS和Backtracking的区别

Backtracking是一种更通用的算法。

深度优先搜索是与搜索树结构相关的特定回溯形式。来自维基百科：

一个从根开始（在图形情况下选择一个节点作为根）并在回溯之前尽可能地沿着每个分支进行探索。

它使用回溯作为其使用树的方法的一部分，但仅限于树结构。

但是，回溯可以用于任何类型的结构，其中可以消除域的部分 - 无论它是否是逻辑树。 Wiki示例使用棋盘和特定问题 - 您可以查看特定的移动，消除它，然后回溯到下一个可能的移动，消除它，等等。

-	DFS	Backtracking
Target Structure	Actual Tree/Graph Structure	Any type of structure where portions of the domain can be eliminated (Chess Board, matrix, implicit tree)
Definition	A specific form of backtracking related to searching tree/graph structures	Traverse from the end and prune unacceptable cases
Start-At Point	Root of the Tree	End of the Goal
Moving Direction	From the root to each branch	From the end moving backwards

搜索问题的解法

DFS（深度优先搜索）
BFS（广度优先搜索）
backtracking（回溯）

DFS模板

void dfs(...) 
{
    // 结束递归的条件
    if (...) {
        ..... // 把“当前结果” 加入 “结果集容器” 中
        return;
    }
    // 继续递归，里面可能有回溯，也可能没有
    if (...) {
        ... // 在容器中保存当前数据
        dfs() 
        ... // 在容器中删除上面保存的数据（注：这种情况下就称为回溯，很明显它是dfs的一个步骤）
    }
}

难点

寻找dfs结束条件
继续dfs的条件

题目

78. Subsets
93. Restore IP Addresses

DFS（回溯）题型：

1） Leetcode 17. Letter Combinations of a Phone Number

Leetcode 22. Generate Parentheses

Leetcode 39. Combination Sum

Leetcode 40. Combination Sum II

Leetcode 46. Permutations

Leetcode 47. Permutations II

Leetcode 77. Combinations

Leetcode 78. Subsets

2）Leetcode 37. Sudoku Solver

BFS模板

模板1

void bfs(...)
{
    queue q;
    q.push(startRoot);
    while (!q.empty()) {
        // 按照节点处理
        curNode = q.front();
        q.pop();
        if (...) {
            // 处理curNode,并把curNode的相邻Nodes加入队列
        }
    }
}

模板2

void bfs(...)
{
    queue q;
    q.push(startRoot);
    while (!q.empty()) {
        // 按照层次处理
        size = q.size();
        for (i = 0; i < size; i++) {
            curNode = q.front();
            q.pop();
            if (... ) {
                // 处理curNode,并把curNode的相邻Nodes加入队列
            }
        }
    }
}