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;
}

四、回溯算法的优化技巧

剪枝：提前终止不可能得到解的路径。
- 条件剪枝：如组合总和问题中的 sum + candidates[i] > target。
- 去重剪枝：如全排列问题中跳过已使用的元素。
排序预处理：对输入数组排序，便于剪枝（如组合总和问题）。
记忆化：记录已访问的状态，避免重复计算（如数独问题）。