企业官网建设流程全解析

深度优先遍历（Depth-First Search, DFS）的核心逻辑就像一位执着的迷宫探险家：选定一条路就一直走到尽头，走不通就退回上一个岔路口，换一条分支继续探索，直到遍历完所有可达路径。它天然契合「递归」的思想，是算法面试中回溯、图论、树形问题的基石。

本篇聚焦 DFS 的基础原理与经典回溯题型，带你从零掌握递归式 DFS 的写法。

例题 1：二叉树的前序遍历

题目：给定一棵二叉树的根节点，返回它节点值的前序遍历（根→左→右）。

思路讲解二叉树是 DFS 最直观的载体。前序遍历的本质就是：先访问当前根节点，再递归深入左子树，左子树全部走完后，再递归深入右子树，完美符合「一条路走到黑」的 DFS 特性。

完整代码（C++）

cpp

运行

#include <iostream> #include <vector> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; class Solution { private: vector<int> res; // 存储遍历结果 // DFS 递归函数：参数为当前访问的节点 void dfs(TreeNode* node) { if (node == nullptr) return; // 递归终止条件：节点为空，退回上一层 res.push_back(node->val); // 1. 处理当前节点（根） dfs(node->left); // 2. 递归遍历左子树（一路向左走到底） dfs(node->right); // 3. 左子树走完后，递归遍历右子树 } public: vector<int> preorderTraversal(TreeNode* root) { res.clear(); dfs(root); // 从根节点开始深度优先遍历 return res; } };

代码详解

• 终止条件：当节点为空时，说明这条分支走到了尽头，直接 return 回溯。
• 递归顺序：根→左→右，每进入一层就先处理当前节点，再优先深入左子树。
• 全局结果数组：在递归函数外部维护结果，每层递归都向其中添加节点值。

例题 2：全排列问题

题目：给定一个不含重复数字的数组nums，返回其所有可能的全排列。

思路讲解全排列是回溯法的入门经典。我们可以把排列过程想象成「依次填每一个位置」：每选一个数字填入当前位置，就标记它为已使用，然后递归填下一个位置；填完所有位置后回溯，撤销标记，尝试下一个可选数字。

完整代码（C++）

cpp

运行

#include <iostream> #include <vector> using namespace std; class Solution { private: vector<vector<int>> result; // 存储所有排列结果 vector<int> path; // 存储当前正在构建的排列 vector<bool> used; // 标记数字是否已被使用 // index：当前要填的位置下标 void dfs(vector<int>& nums, int index) { // 递归终止：排列长度等于数组长度，说明找到一个完整排列 if (index == nums.size()) { result.push_back(path); return; } // 遍历所有数字，选一个没使用过的填入当前位置 for (int i = 0; i < nums.size(); i++) { if (used[i]) continue; // 已使用，跳过 used[i] = true; // 标记为已使用 path.push_back(nums[i]); // 填入当前位置 dfs(nums, index + 1); // 递归填下一个位置 path.pop_back(); // 回溯：撤销当前选择 used[i] = false; // 回溯：取消使用标记 } } public: vector<vector<int>> permute(vector<int>& nums) { result.clear(); path.clear(); used.resize(nums.size(), false); dfs(nums, 0); return result; } };

代码详解

• 状态变量：path记录当前路径，used记录可选状态，index记录当前深度。
• 回溯核心：递归调用之后，必须对称地撤销选择（弹出元素、取消标记），回到上一层状态。
• 时间复杂度：O (n×n!)，n 个元素共有 n! 种排列，每种排列需要 O (n) 时间存入结果。

例题 3：子集问题

题目：给你一个整数数组nums，数组中的元素互不相同，返回该数组所有可能的子集。

思路讲解子集问题的核心是「每个元素可选可不选」。DFS 过程中，每遇到一个元素，都有两条分支：选它加入子集，或者不选；我们通过控制起始下标来避免重复子集，保证元素按顺序选取。

完整代码（C++）

cpp

运行

#include <iostream> #include <vector> using namespace std; class Solution { private: vector<vector<int>> result; vector<int> path; // start：当前可选元素的起始下标 void dfs(vector<int>& nums, int start) { result.push_back(path); // 每进入一层，当前路径就是一个子集，直接加入结果 // 从 start 开始遍历，避免重复选取前面的元素 for (int i = start; i < nums.size(); i++) { path.push_back(nums[i]); // 选择第 i 个元素 dfs(nums, i + 1); // 递归，下一层只能从 i+1 开始选 path.pop_back(); // 回溯：撤销选择 } } public: vector<vector<int>> subsets(vector<int>& nums) { result.clear(); path.clear(); dfs(nums, 0); return result; } };

代码详解

• 关键点：start下标是子集问题的灵魂，它保证了元素只被选一次，不会出现[1,2]和[2,1]这种重复。
• 结果收集时机：每进入一层递归就收集一次结果，因为空集、单元素、多元素都是合法子集。
• 递归终止：当i超出数组范围时，循环自然结束，函数自动回溯。

例题 4：组合总和

题目：给定一个无重复元素的正整数数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合，数字可以无限制重复选取。

思路讲解这是带「剪枝」的经典回溯题。由于数字可重复选，下一层递归的起始下标仍是i而非i+1；同时我们可以对数组排序，当当前和超过 target 时，直接终止后续分支，实现剪枝提速。

完整代码（C++）

cpp

运行

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { private: vector<vector<int>> result; vector<int> path; // start：起始下标；sum：当前路径的和 void dfs(vector<int>& candidates, int start, int sum, int target) { if (sum == target) { result.push_back(path); return; } for (int i = start; i < candidates.size(); i++) { // 剪枝：当前数字加入后超过目标，后续更大的数字也都会超过，直接 break if (sum + candidates[i] > target) break; path.push_back(candidates[i]); dfs(candidates, i, sum + candidates[i], target); // 下标不传 i+1，允许重复选 path.pop_back(); } } public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { result.clear(); path.clear(); sort(candidates.begin(), candidates.end()); // 排序是剪枝的前提 dfs(candidates, 0, 0, target); return result; } };

代码详解

• 重复选取的关键：递归时start传i，表示下一层仍可以选当前数字。
• 剪枝优化：排序后，一旦sum + candidates[i] > target，后面的元素更大，无需再遍历，直接跳出循环。
• 终止条件：当前路径和等于 target 时，收集结果并回溯。