DFS（深度优先搜索）与回溯算法详解

---

一、DFS 基础

1. 什么是DFS？
深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。其核心思想是：

• 一条路走到黑：从起点出发，尽可能深入未访问的分支，直到无法继续前进。
• 回溯：当走到尽头时，回退到上一个分叉点，选择另一条未探索的路径继续深入。

2. DFS 的实现方式
DFS 可以通过两种方式实现：

• 递归：利用函数调用栈隐式实现回溯。
• 显式栈：手动维护一个栈来模拟递归过程。

示例：二叉树的DFS遍历

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

// 递归实现DFS（前序遍历）
void dfs(TreeNode* root) {
    if (!root) return;
    cout << root->val << " "; // 访问当前节点
    dfs(root->left);          // 递归左子树
    dfs(root->right);         // 递归右子树
}

---

二、回溯算法

1. 什么是回溯？
回溯（Backtracking）是一种通过“试错”寻找问题解的算法。它在DFS的基础上，通过剪枝（Pruning）避免无效搜索，通常用于解决组合、排列、子集等需要穷举所有可能性的问题。

2. 回溯的核心步骤

• 选择：在当前状态下，做出一个可能的决策。
• 递归：基于这个决策，进入下一层递归。
• 撤销：递归返回后，撤销当前决策，回到之前的状态（即“回溯”）。

3. 回溯模板

void backtrack(路径, 选择列表) {
    if (满足终止条件) {
        将路径加入结果集;
        return;
    }

    for (选择 : 选择列表) {
        if (选择不合法) continue;  // 剪枝
        
        做出选择;           // 将选择加入路径
        backtrack(新路径, 新选择列表);
        撤销选择;           // 将选择从路径中移除（回溯）
    }
}

---

三、经典问题与代码实现

1. 全排列问题
问题描述：给定无重复元素的数组 [1,2,3]，返回所有可能的排列。
示例代码：

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used(nums.size(), false); // 记录元素是否被使用

    function<void()> backtrack = [&]() {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue; // 剪枝：已使用的元素跳过
            used[i] = true;        // 做出选择
            path.push_back(nums[i]);
            backtrack();
            path.pop_back();       // 撤销选择
            used[i] = false;
        }
    };

    backtrack();
    return res;
}

2. 组合总和问题
问题描述：给定候选数组 [2,3,6,7] 和目标值 7，找出所有和为 7 的组合（元素可重复使用）。
示例代码：

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> path;
    sort(candidates.begin(), candidates.end()); // 排序便于剪枝

    function<void(int, int)> backtrack = [&](int start, int sum) {
        if (sum == target) {
            res.push_back(path);
            return;
        }
        for (int i = start; i < candidates.size(); i++) {
            if (sum + candidates[i] > target) break; // 剪枝：超过目标值跳过
            path.push_back(candidates[i]);
            backtrack(i, sum + candidates[i]); // 允许重复使用元素（i不+1）
            path.pop_back();
        }
    };

    backtrack(0, 0);
    return res;
}

3. N皇后问题
问题描述：在 N×N 的棋盘上放置 N 个皇后，使得它们不能互相攻击。
示例代码：

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.')); // 初始化棋盘

    function<bool(int, int)> isValid = [&](int row, int col) {
        // 检查列是否有冲突
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') return false;
        }
        // 检查左上对角线
        for (int i = row-1, j = col-1; i >=0 && j >=0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 检查右上对角线
        for (int i = row-1, j = col+1; i >=0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    };

    function<void(int)> backtrack = [&](int row) {
        if (row == n) {
            res.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!isValid(row, col)) continue; // 剪枝：非法位置跳过
            board[row][col] = 'Q'; // 放置皇后
            backtrack(row + 1);    // 处理下一行
            board[row][col] = '.'; // 回溯
        }
    };

    backtrack(0);
    return res;
}

---

四、回溯算法的优化技巧

1. 剪枝：提前终止不可能得到解的路径。

   • 条件剪枝：如组合总和问题中的 sum + candidates[i] > target。
   • 去重剪枝：如全排列问题中跳过已使用的元素。

2. 排序预处理：对输入数组排序，便于剪枝（如组合总和问题）。

3. 记忆化：记录已访问的状态，避免重复计算（如数独问题）。

---

五、DFS与回溯的关系

• DFS 是回溯的实现方式：回溯算法通常通过递归的DFS实现。
• 回溯是DFS的应用场景：DFS用于遍历所有可能性，回溯通过剪枝优化DFS的效率。
• 区别：
  • DFS 更强调遍历所有路径（如二叉树的遍历）。
  • 回溯 更强调通过试错寻找解（如组合、排列问题）。

---

六、总结

• DFS 是遍历树或图的算法，核心是“一条路走到黑”。
• 回溯 是基于DFS的优化策略，通过“试错+剪枝”寻找问题的解。
• 关键步骤：选择 → 递归 → 撤销选择（回溯）。
• 经典问题：全排列、组合总和、N皇后、子集、数独等。

---

练习题

1. 实现子集问题（返回数组的所有子集）。
2. 解决数独问题（填充所有空格）。
3. 优化全排列代码，处理输入数组包含重复元素的情况。