深度优先遍历Depth-First Search, DFS的核心逻辑就像一位执着的迷宫探险家选定一条路就一直走到尽头走不通就退回上一个岔路口换一条分支继续探索直到遍历完所有可达路径。它天然契合「递归」的思想是算法面试中回溯、图论、树形问题的基石。本篇聚焦 DFS 的基础原理与经典回溯题型带你从零掌握递归式 DFS 的写法。例题 1二叉树的前序遍历题目给定一棵二叉树的根节点返回它节点值的前序遍历根→左→右。思路讲解二叉树是 DFS 最直观的载体。前序遍历的本质就是先访问当前根节点再递归深入左子树左子树全部走完后再递归深入右子树完美符合「一条路走到黑」的 DFS 特性。完整代码Ccpp运行#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: vectorint 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: vectorint preorderTraversal(TreeNode* root) { res.clear(); dfs(root); // 从根节点开始深度优先遍历 return res; } };代码详解终止条件当节点为空时说明这条分支走到了尽头直接 return 回溯。递归顺序根→左→右每进入一层就先处理当前节点再优先深入左子树。全局结果数组在递归函数外部维护结果每层递归都向其中添加节点值。例题 2全排列问题题目给定一个不含重复数字的数组nums返回其所有可能的全排列。思路讲解全排列是回溯法的入门经典。我们可以把排列过程想象成「依次填每一个位置」每选一个数字填入当前位置就标记它为已使用然后递归填下一个位置填完所有位置后回溯撤销标记尝试下一个可选数字。完整代码Ccpp运行#include iostream #include vector using namespace std; class Solution { private: vectorvectorint result; // 存储所有排列结果 vectorint path; // 存储当前正在构建的排列 vectorbool used; // 标记数字是否已被使用 // index当前要填的位置下标 void dfs(vectorint 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: vectorvectorint permute(vectorint 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 过程中每遇到一个元素都有两条分支选它加入子集或者不选我们通过控制起始下标来避免重复子集保证元素按顺序选取。完整代码Ccpp运行#include iostream #include vector using namespace std; class Solution { private: vectorvectorint result; vectorint path; // start当前可选元素的起始下标 void dfs(vectorint 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); // 递归下一层只能从 i1 开始选 path.pop_back(); // 回溯撤销选择 } } public: vectorvectorint subsets(vectorint nums) { result.clear(); path.clear(); dfs(nums, 0); return result; } };代码详解关键点start下标是子集问题的灵魂它保证了元素只被选一次不会出现[1,2]和[2,1]这种重复。结果收集时机每进入一层递归就收集一次结果因为空集、单元素、多元素都是合法子集。递归终止当i超出数组范围时循环自然结束函数自动回溯。例题 4组合总和题目给定一个无重复元素的正整数数组candidates和一个目标数target找出candidates中所有可以使数字和为target的组合数字可以无限制重复选取。思路讲解这是带「剪枝」的经典回溯题。由于数字可重复选下一层递归的起始下标仍是i而非i1同时我们可以对数组排序当当前和超过 target 时直接终止后续分支实现剪枝提速。完整代码Ccpp运行#include iostream #include vector #include algorithm using namespace std; class Solution { private: vectorvectorint result; vectorint path; // start起始下标sum当前路径的和 void dfs(vectorint 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); // 下标不传 i1允许重复选 path.pop_back(); } } public: vectorvectorint combinationSum(vectorint 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 时收集结果并回溯。谢谢