【每日算法】Day 10-1：深度优先搜索（DFS）算法精讲——排列组合与路径问题的终极解法（C++实现）

解锁回溯与遍历的核心能力！今日深入解析深度优先搜索（DFS）的实现原理与优化技巧，结合排列组合、路径搜索等高频场景，彻底掌握递归与剪枝的底层逻辑。

一、DFS 核心思想

深度优先搜索（DFS） 是一种优先探索分支路径到底层的算法，核心特性：

递归/栈驱动：通过递归调用栈或显式栈实现深度遍历

路径探索：适合寻找所有可能解或连通性检测

回溯机制：通过状态重置实现多路径搜索

适用场景：

排列组合问题（全排列、子集）
矩阵/图中的路径搜索（岛屿问题、迷宫问题）
树形结构遍历（路径总和、二叉树操作）

二、DFS 算法模板

1. 递归模板（隐式栈）

void dfs(参数列表) {if (终止条件) { 记录结果; return; }for (选择 in 选择列表) {处理选择;    // 前序操作dfs(新参数); // 递归进入下一层撤销选择;    // 后序操作（回溯）}
}

2. 迭代模板（显式栈）

void dfsIterative(Node* root) {stack<Node*> stk;unordered_set<Node*> visited;stk.push(root);while (!stk.empty()) {Node* curr = stk.top(); stk.pop();if (visited.count(curr)) continue;visited.insert(curr);// 处理当前节点for (auto& neighbor : curr->neighbors) {stk.push(neighbor); // 按逆序入栈保证顺序}}
}

三、四大高频应用场景

场景1：全排列问题（LeetCode 46）

vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;function<void(int)> dfs = [&](int start) {if (start == nums.size()) {res.push_back(nums);return;}for (int i = start; i < nums.size(); ++i) {swap(nums[start], nums[i]); // 选择当前位dfs(start + 1);             // 递归后续位swap(nums[start], nums[i]); // 撤销选择}};dfs(0);return res;
}

场景2：岛屿数量（LeetCode 200）

int numIslands(vector<vector<char>>& grid) {int count = 0;for (int i = 0; i < grid.size(); ++i) {for (int j = 0; j < grid[0].size(); ++j) {if (grid[i][j] == '1') {dfs(grid, i, j);count++;}}}return count;
}void dfs(vector<vector<char>>& grid, int x, int y) {if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] != '1') return;grid[x][y] = '0'; // 标记为已访问dfs(grid, x + 1, y);dfs(grid, x - 1, y);dfs(grid, x, y + 1);dfs(grid, x, y - 1);
}

场景3：路径总和 III（LeetCode 437）

int pathSum(TreeNode* root, int targetSum) {unordered_map<long, int> prefix; // 前缀和计数prefix[0] = 1; // 初始前缀和为0出现1次int count = 0;function<void(TreeNode*, long)> dfs = [&](TreeNode* node, long currSum) {if (!node) return;currSum += node->val;// 查找当前路径是否存在前缀和满足 currSum - targetSumcount += prefix[currSum - targetSum];prefix[currSum]++; // 记录当前前缀和dfs(node->left, currSum);dfs(node->right, currSum);prefix[currSum]--; // 回溯};dfs(root, 0);return count;
}

场景4：组合总和（LeetCode 39）

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)> dfs = [&](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]);dfs(i, sum + candidates[i]); // 允许重复选择path.pop_back();}};dfs(0, 0);return res;
}

四、DFS 优化技巧

优化方法	应用场景	优化效果
记忆化搜索	重复子问题（如斐波那契）	时间复杂度降为O(n)
剪枝策略	排列组合问题	减少无效递归路径
前缀和+哈希表	路径总和问题	时间复杂度降为O(n)
双向DFS	状态空间较大问题	减少搜索空间

五、大厂真题实战

真题1：单词搜索（某大厂2024面试）

题目描述：
在二维字符矩阵中搜索给定单词是否存在（相邻字母连接）
DFS解法：

bool exist(vector<vector<char>>& board, string word) {for (int i = 0; i < board.size(); ++i) {for (int j = 0; j < board[0].size(); ++j) {if (dfs(board, word, i, j, 0)) return true;}}return false;
}bool dfs(vector<vector<char>>& board, string& word, int x, int y, int idx) {if (idx == word.size()) return true;if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] != word[idx]) return false;char tmp = board[x][y];board[x][y] = '#'; // 标记已访问bool found = dfs(board, word, x+1, y, idx+1)|| dfs(board, word, x-1, y, idx+1)|| dfs(board, word, x, y+1, idx+1)|| dfs(board, word, x, y-1, idx+1);board[x][y] = tmp; // 回溯return found;
}

真题2：N皇后问题（某大厂2023笔试）

题目描述：
在N×N棋盘放置N个皇后，使其互不攻击
DFS+位运算优化：

vector<vector<string>> solveNQueens(int n) {vector<vector<string>> res;vector<string> board(n, string(n, '.'));function<void(int, int, int, int)> dfs = [&](int row, int cols, int diag1, int diag2) {if (row == n) {res.push_back(board);return;}int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);while (available) {int pos = available & -available; // 取最低位的1int col = __builtin_ctz(pos); // 计算列索引board[row][col] = 'Q';dfs(row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1);board[row][col] = '.';available &= available - 1; // 移除最低位的1}};dfs(0, 0, 0, 0);return res;
}

六、复杂度分析

问题类型	时间复杂度	空间复杂度	示例
全排列	O(n×n!)	O(n)	排列问题
组合问题	O(C(n,k)×k)	O(k)	组合总和
矩阵路径搜索	O(3^k)（k为路径长度）	O(k)	单词搜索
树形遍历	O(n)	O(h)	二叉树路径总和