核心感悟递归不仅是函数调用更是一种“问题拆解”的艺术。无论是把环拆成链还是把 K 个链表拆成两两合并本质都是降低维度的降维打击。一、 DFS 核心心法状态与回溯深度优先搜索DFS的本质是在一棵隐式的决策树上进行遍历。节点代表当前的状态如走到了哪里、选了哪些数。边代表做出的选择如向右走、选择数字 3。回溯当一条路走不通或走完后退回上一个节点恢复状态尝试下一条路。1. 通用 DFS 模板// 全局状态定义 int visited[N]; // 标记访问状态防重复/走回头路 int path[N]; // 记录当前路径 int path_len; // 当前路径长度 void dfs(当前状态) { // 1. 终止条件找到解 or 无法继续 if (到达目标) { 记录结果(path); return; } // 2. 剪枝可选提前排除无效分支 if (当前状态非法) return; // 3. 遍历所有选择 for (每个选择 choice) { // 4. 做选择 visited[choice] 1; path[path_len] choice; // 5. 深入下一层 dfs(新状态); // 6. 撤销选择回溯的关键 visited[choice] 0; path_len--; } }二、 基础模型三大枚举问题1. 字符串/数组全排列Permutation场景打乱顺序每个元素只能用一次。关键点使用used数组标记占用情况。#include stdio.h #include string.h #define MAX 7 char str[MAX], result[MAX]; int used[MAX], len; void dfs(int depth) { // 边界排列完成 if (depth len) { result[depth] \0; printf(%s\n, result); return; } // 遍历所有字符 for (int i 0; i len; i) { if (!used[i]) { used[i] 1; // 1. 做选择占用 result[depth] str[i]; // 放入路径 dfs(depth 1); // 递归下一层 used[i] 0; // 2. 撤销选择释放回溯 } } } int main() { scanf(%s, str); len strlen(str); memset(used, 0, sizeof(used)); dfs(0); return 0; }2. 组合型枚举Combination场景从 n 个数中选 m 个不重不漏且通常要求升序。关键点传递起点参数Next Start确保下一层只能选比当前大的数保证不重。#include stdio.h int arr[10]; // 暂存结果 // place: 当前要填第几个位置 // start: 当前可选数字的最小值起始下标 void combine(int place, int start, int n, int m) { // 边界 1已经选够了 m 个数 if (m 0) { for (int i 0; i place; i) printf(%d , arr[i]); printf(\n); return; } // 剪枝剩下的数不够选了比如还需选3个但从start到n只剩2个数了 if (n - start 1 m) return; // 遍历当前位置所有可能的选择 for (int k start; k n; k) { arr[place] k; // 填入当前位置 // 核心逻辑选了 k 之后下一个位置只能从 k1 开始选保证递增 combine(place 1, k 1, n, m - 1); // 无需显式撤销选择因为下次循环 arr[place] 会被覆盖 } } int main() { int n, m; scanf(%d%d, n, m); combine(0, 1, n, m); // 从第0个位置开始起始数字为1 return 0; }3. 指数型枚举Exponential Enumeration / 子集问题场景从 n 个数中选任意多个包括空集。关键点对于每一个数只有两种状态选或不选。#include stdio.h int arr[10]; // cur: 当前考察的数字 // place: 当前结果数组的下标 void subset(int place, int cur, int n) { // 边界考察完所有数字 if (cur n) { for (int i 0; i place; i) printf(%d , arr[i]); printf(\n); return; } // 选择 1要当前数 arr[place] cur; subset(place 1, cur 1, n); // place1cur1 // 选择 2不要当前数回溯体现在 place 不变只移动 cur subset(place, cur 1, n); } int main() { int n; scanf(%d, n); subset(0, 1, n); return 0; }三、 进阶实战DFS 在复杂问题中的应用1. 走迷宫路径记录场景寻找从起点到终点的所有路径简化版只能右走或下走。技巧使用全局数组path记录路径递归前后维护索引。#include stdio.h char path[10]; int path_index 0; void print_path() { for (int k 0; k path_index; k) printf(%c, path[k]); printf(\n); } // i, j 代表当前坐标 void dfs_maze(int i, int j) { // 假设终点是 (2, 2) if (i 2 j 2) { print_path(); return; } // 选择 1向右走边界检查 if (j 2) { path[path_index] R; // 记录路径 dfs_maze(i, j 1); path_index--; // 回溯撤销记录 } // 选择 2向下走边界检查 if (i 2) { path[path_index] D; dfs_maze(i 1, j); path_index--; } } int main() { dfs_maze(0, 0); return 0; }四、 今日刷题1. LeetCode 213打家劫舍 II环形拆解问题房子围成一圈首尾不能同时偷。 突破点既然首尾相连导致冲突那就拆环为链。情况 A偷第一家不能偷最后一家范围[0, n-2]。情况 B不偷第一家可以偷最后一家范围[1, n-1]。代码实现线性 DP 环形拆解int rob_range(int* nums, int start, int end) { if (start end) return 0; int prev2 0, prev1 nums[start]; for (int i start 1; i end; i) { int curr (prev2 nums[i] prev1) ? (prev2 nums[i]) : prev1; prev2 prev1; prev1 curr; } return prev1; } int rob(int* nums, int numsSize) { if (numsSize 0) return 0; if (numsSize 1) return nums[0]; // 核心拆分成两个线性问题取最大值 int m rob_range(nums, 0, numsSize - 2); int n rob_range(nums, 1, numsSize - 1); return m n ? m : n; }2. LeetCode 23合并 K 个升序链表递归分治问题合并 K 个有序链表。 突破点不要一次性合并 K 个而是两两合并分治思想。递归逻辑取出最后两个链表合并。将结果放回数组。递归处理剩下的k-1个链表。代码实现/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode dummy {0, NULL}; struct ListNode* tail dummy; while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; } tail-next l1 ? l1 : l2; return dummy.next; } struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) { if (listsSize 0) return NULL; if (listsSize 1) return lists[0]; // 递归两两合并减少一个链表 lists[listsSize - 2] mergeTwoLists(lists[listsSize - 2], lists[listsSize - 1]); // 递归处理剩下的 k-1 个 return mergeKLists(lists, listsSize - 1); } 改进建议虽然递归写法很优雅但在 LeetCode 提交时可能会遇到栈溢出Stack Overflow的风险尤其是链表极长时。更优方案使用优先队列最小堆。将所有链表的头节点放入最小堆。每次弹出最小的节点将其下一个节点压入堆。时间复杂度O(N \log K)且空间复杂度更稳定。五、 总结问题类型核心参数设计关键操作排列 (Permutation)(depth, used[])遍历所有未使用的元素组合 (Combination)(pos, start)限制下一次选择的起点子集 (Subset)(pos, cur)二元选择选或不选环形 DP(range_start, range_end)分类讨论拆解为线性递归的魅力在于不要去想递归的具体步骤只需要定义好“当前层做什么”以及“交给下一层什么任务”。