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

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. 优化全排列代码，处理输入数组包含重复元素的情况。