DFS

题目要求 输入输出 输入：nums，长度 1 <= nums.length <= 10 元素范围：-10 <= nums[i] <= 10 所有元素互不相同 输出：返回 nums 的所有可能子集 顺序：结果顺序不限，子集内部不需要考虑排列顺序 示例 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 这篇只用 Python 构造一个最小可运行解法。 从 [1,2] 的搜索树开始 最小但有分叉的例子是： nums = [1,2] 答案应该是： [], [1], [1,2], [2] 注意这里没有 [2,1]。这说明问题不是“随便排列所有选择”，而是“每个元素选或不选，且同一组元素只出现一次”。 如果把构造过程画成树： [] |- [1] | |- [1,2] |- [2] 这棵树暴露出两个事实： 每个节点都是一个合法子集。 进入 [1] 之后，后面只能继续看 2，不能回头再选 1 或生成 [2,1]。 Step 1：先说清楚一个递归层在解决什么 如果当前已经选出一个 path，剩下的问题是： 从某个起点之后的元素里，继续选择若干个元素，扩展当前 path。 这个“某个起点”必须被记下来。否则 [1,2] 和 [2,1] 会从不同路径重复出现。 先写最小骨架。它只保留两个状态： ...

副标题 / 摘要 LeetCode 124 最容易混淆的地方是：递归到底该返回“整条最大路径”还是“能继续向上接的那一段贡献”。只要把这两个角色分开，这题就会变成一个非常典型的树形 DP。 预计阅读时长：12~15 分钟 标签：Hot100、二叉树、树形DP、DFS、后序遍历 SEO 关键词：Binary Tree Maximum Path Sum, 二叉树中的最大路径和, 树形DP, 单边贡献, 后序遍历, LeetCode 124 元描述：系统讲透 LeetCode 124 的单边贡献返回值、全局最大路径更新、负贡献剪枝与多语言实现。 A — Algorithm（题目与算法） 题目还原 二叉树中的一条路径定义为： 由若干个节点组成 相邻节点之间必须有边相连 同一个节点在一条路径里最多出现一次 路径至少包含一个节点 路径不一定经过根节点 路径和就是路径上所有节点值之和。 题目要求返回整棵树里的最大路径和。 输入输出 名称 类型 描述 root TreeNode 二叉树根节点 返回值 int 最大路径和 示例 1 输入：root = [1,2,3] 输出：6 解释：最优路径是 2 -> 1 -> 3，路径和为 6。 示例 2 输入：root = [-10,9,20,null,null,15,7] 输出：42 解释：最优路径是 15 -> 20 -> 7，路径和为 42。 提示 树中节点数目范围是 [1, 3 * 10^4] -1000 <= Node.val <= 1000 目标读者 已经做过 543，但还没完全理解“树上路径题”返回值该如何设计的学习者 一写最大路径和就会把“经过当前节点的完整路径”和“向上返回的贡献”混掉的开发者 想系统掌握树形 DP 基本套路的读者 背景 / 动机 这题的关键训练点是： ...

副标题 / 摘要 LeetCode 543 最容易混乱的点是：递归函数到底应该返回“高度”还是“直径”。这题的稳定写法是后序遍历时向上返回高度，同时在每个节点尝试更新“经过当前节点的最长路径”。理解这个分工后，树形 DP 会一下子清楚很多。 预计阅读时长：10~13 分钟 标签：Hot100、二叉树、树形DP、DFS、后序遍历 SEO 关键词：Diameter of Binary Tree, 二叉树的直径, 树形DP, 高度回传, DFS, LeetCode 543 元描述：系统讲透 LeetCode 543 的后序高度回传法，包含递推推导、工程迁移、复杂度分析与多语言实现。 A — Algorithm（题目与算法） 题目还原 给你一棵二叉树的根节点 root，返回该树的直径。 二叉树的直径指的是： 树中任意两个节点之间最长路径的长度 这条路径可以经过根节点，也可以不经过根节点 路径长度按边数计算 输入输出 名称 类型 描述 root TreeNode 二叉树根节点 返回 int 树的直径（最长路径边数） 示例 1 输入：root = [1,2,3,4,5] 输出：3 解释：长度为 3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 。 示例 2 输入：root = [1,2] 输出：1 提示 树中节点数目在范围 [1, 10^4] 内 -100 <= Node.val <= 100 目标读者 已经会写树深度递归，准备进入树形 DP 视角的学习者 容易把“返回值”和“全局答案”混在一起的开发者 在工程里处理层级传播链、最长链路或树状结构跨度问题的工程师 背景 / 动机 看到“二叉树的直径”，很多人第一反应会是： ...

副标题 / 摘要 LeetCode 236 的真正难点不是“记住 LCA 模板”，而是先定义清楚：递归函数到底要向父节点返回什么信息。只要这个返回值语义稳定，整题就会自然落成一段非常短但非常强的后序递归。 预计阅读时长：11~14 分钟 标签：Hot100、二叉树、LCA、DFS、后序遍历 SEO 关键词：Lowest Common Ancestor of a Binary Tree, 二叉树的最近公共祖先, LCA, 后序遍历, DFS, LeetCode 236 元描述：系统讲透 LeetCode 236 的后序返回值定义、节点自祖先规则、递归推导过程、工程迁移和多语言实现。 A — Algorithm（题目与算法） 题目还原 给定一棵二叉树，找到该树中两个指定节点 p 和 q 的最近公共祖先。 最近公共祖先（LCA）的定义是： x 同时是 p 和 q 的祖先 在满足上面条件的节点里，x 的深度尽可能大 一个节点也可以是它自己的祖先 输入输出 名称 类型 描述 root TreeNode 二叉树根节点 p, q TreeNode 树中的两个指定节点；示例输入里用它们的唯一值表示 返回 TreeNode p 和 q 的最近公共祖先 示例 1 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3 输入：root = [1,2], p = 1, q = 2 输出：1 提示 树中节点数目在范围 [2, 10^5] 内 -10^9 <= Node.val <= 10^9 所有 Node.val 互不相同 p != q p 和 q 均存在于给定的二叉树中 目标读者 已经会写普通树递归，但一到“最近公共祖先”就容易卡在返回值定义上的学习者 想把后序分治写法固定成稳定模板的开发者 在工程里处理组织树、组件树、目录树共享祖先问题的工程师 背景 / 动机 很多人第一次做 236，会下意识想到： ...

副标题 / 摘要 LeetCode 98 最容易写错的地方，不是“不会递归”，而是误以为每个节点只要和自己的父节点比较就够了。真正的 BST 校验要把祖先留下来的上下界一路向下传递。本文按 ACERS 结构把这个不变量讲透，再补上中序遍历判序的等价视角。 预计阅读时长：11~14 分钟 标签：Hot100、二叉树、BST、DFS、中序遍历 SEO 关键词：Validate Binary Search Tree, 验证二叉搜索树, BST, 区间约束, 中序遍历, LeetCode 98 元描述：系统讲透 LeetCode 98 的区间递归写法与中序递增判定思路，包含推导、工程迁移、多语言实现与高频误区。 A — Algorithm（题目与算法） 题目还原 给你一个二叉树的根节点 root，判断它是否是一棵有效的二叉搜索树（BST）。 有效 BST 需要同时满足： 左子树所有节点值都严格小于当前节点值 右子树所有节点值都严格大于当前节点值 左右子树本身也都必须是 BST 输入输出 名称 类型 描述 root TreeNode 二叉树根节点 返回 bool 是否为有效 BST 示例 1 输入：root = [2,1,3] 输出：true 示例 2 输入：root = [5,1,4,null,null,3,6] 输出：false 解释：根节点的值是 5，但是右子节点的值是 4 。 提示 树中节点数目范围在 [1, 10^4] 内 -2^31 <= Node.val <= 2^31 - 1 目标读者 刷 Hot100，准备把 BST 判断模板彻底固定下来的学习者 会写树递归，但一遇到“全局约束”就容易只写局部判断的开发者 在工程里处理树形有序结构、范围规则树、层级校验逻辑的工程师 背景 / 动机 这题看起来像一题“简单树递归”，但它真正训练的是： ...

副标题 / 摘要 216. 组合总和 III 给回溯再加了一条关键约束：不仅总和要命中，组合长度也必须恰好等于 k。这会把问题变成一个很干净的“固定长度组合搜索”。 预计阅读时长：12~15 分钟 标签：回溯、固定长度、剪枝、组合搜索 SEO 关键词：Combination Sum III, 组合总和 III, 固定长度回溯, k 个数, 剪枝, LeetCode 216 元描述：从题目本身推导 LeetCode 216 的稳定解法，真正理解固定长度 k、有界候选集 1..9 与只能使用一次的回溯模型。 A — Algorithm（题目与算法） 题目还原 找出所有满足条件的组合，使得： 从 1 到 9 中选数 一共恰好选 k 个数 这些数的和等于 n 每个数最多只能使用一次 返回所有可能的合法组合。 答案中不能包含重复组合，组合顺序不重要。 输入输出 名称 类型 描述 k int 需要选出的数字个数 n int 目标和 返回 int[][] 所有长度为 k 且和为 n 的合法组合 示例 1 输入：k = 3, n = 7 输出：[[1,2,4]] 示例 2 输入：k = 3, n = 9 输出：[[1,2,6],[1,3,5],[2,3,4]] 示例 3 输入：k = 4, n = 1 输出：[] 约束 2 <= k <= 9 1 <= n <= 60 目标读者 已经理解 39、40，现在准备继续叠加“长度必须恰好是 k”这个新约束的学习者 会写基本 DFS，但经常把“目标和”与“固定长度”混在一起判断的读者 想掌握固定长度组合搜索模板的开发者 背景 / 动机 这道题很适合作为 39 和 40 之后的下一题，因为它保留了回溯骨架，但搜索空间进一步收紧了： ...

副标题 / 摘要 如果说 39. 组合总和 教你“当前值还能继续用”，那 40. 组合总和 II 教你的就是下一层升级：数组里会出现重复值、每个位置只能用一次、去重必须发生在正确的树层上。 预计阅读时长：14~16 分钟 标签：回溯、去重、剪枝、组合搜索 SEO 关键词：Combination Sum II, 组合总和 II, 回溯, 同层去重, 剪枝, LeetCode 40 元描述：从题目本身一步一步推出 LeetCode 40 的稳定解法，真正理解排序、i + 1 递归和“同层去重”规则。 A — Algorithm（题目与算法） 题目还原 给定一个候选数组 candidates 和一个目标值 target， 找出所有和为 target 的不同组合，并以列表形式返回。 candidates 中的每个数字在每个组合里 最多只能使用一次。 最终答案中不能包含重复组合。 输入输出 名称 类型 描述 candidates int[] 候选数组，允许出现重复值 target int 目标和 返回 int[][] 所有和为 target 的不同组合 示例 1 输入：candidates = [10,1,2,7,6,1,5], target = 8 输出： [ [1,1,6], [1,2,5], [1,7], [2,6] ] 示例 2 输入：candidates = [2,5,2,1,2], target = 5 输出： [ [1,2,2], [5] ] 约束 1 <= candidates.length <= 100 1 <= candidates[i] <= 50 1 <= target <= 30 目标读者 已经做完 39. 组合总和，想继续搞清“不能重复选”之后模板怎么变的学习者 会写回溯框架，但一碰到输入里有重复值就容易写乱去重逻辑的读者 想真正掌握“同层去重”而不是硬背一句 if i > start and ... 的开发者 背景 / 动机 这道题是 39 的自然下一题，因为它同时改了两条规则： ...

副标题 / 摘要 这题表面上像字符串题，实质上是一个非常标准的固定层数回溯模型：第 k 层只处理第 k 个数字，从其映射字母里选一个，直到路径长度等于输入长度。 预计阅读时长：10~12 分钟 标签：Hot100、回溯、字符串、DFS SEO 关键词：Letter Combinations of a Phone Number, 电话号码的字母组合, 回溯, DFS 元描述：用 LeetCode 17 建立固定层数 DFS 模板，理解字符映射、路径长度终止与多语言实现。 A — Algorithm（题目与算法） 题目还原 给定一个仅由数字 2 到 9 组成的字符串 digits，返回它能表示的所有字母组合。 答案顺序不限。数字与字母的映射与电话按键一致，1 不对应任何字母。 输入输出 名称 类型 描述 digits string 由 2 到 9 组成的数字串 返回 string[] 所有可能的字母组合 示例 1 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] 示例 2 输入：digits = "2" 输出：["a","b","c"] 提示 1 <= digits.length <= 4 digits[i] 是范围 ['2', '9'] 内的一个数字 目标读者 已经掌握 78 / 46，准备看另一类回溯树形态的学习者 想把“每层处理一个位置”这种 DFS 模型固定下来的开发者 需要做编码扩展、短串生成、候选串组合的工程师 背景 / 动机 这题和子集、排列都不太一样。 ...

副标题 / 摘要 如果说子集题教你“组合型回溯”的骨架，那么全排列题教你的就是“状态型回溯”的核心：当前位置要选一个还没用过的元素，直到路径长度等于 n 才收集答案。 预计阅读时长：10~12 分钟 标签：Hot100、回溯、全排列、DFS SEO 关键词：Permutations, 全排列, 回溯, used, DFS 元描述：通过 LeetCode 46 固定排列型回溯模板，重点理解 used[]、叶子收集与多语言实现。 A — Algorithm（题目与算法） 题目还原 给定一个不含重复数字的数组 nums，返回它的所有可能全排列。 答案顺序不限。 输入输出 名称 类型 描述 nums int[] 不含重复元素的整数数组 返回 int[][] 所有可能的全排列 示例 1 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2 输入：nums = [0,1] 输出：[[0,1],[1,0]] 示例 3 输入：nums = [1] 输出：[[1]] 提示 1 <= nums.length <= 6 -10 <= nums[i] <= 10 nums 中所有整数互不相同 目标读者 已经做完 78. 子集，准备进入排列型回溯的学习者 会写递归，但状态恢复经常出错的开发者 需要枚举任务执行顺序、测试顺序或操作序列的工程师 背景 / 动机 排列问题和组合问题最本质的区别是： ...

副标题 / 摘要 组合总和是 Hot100 回溯阶段里第一道真正把“组合模板 + 目标约束 + 排序剪枝”揉在一起的题。你不应该直接背结论，而应该顺着问题一步步推出：为什么要有 path，为什么要有 remain，为什么下一层仍然从 i 开始。 预计阅读时长：14~16 分钟 标签：Hot100、回溯、组合、剪枝 SEO 关键词：Combination Sum, 组合总和, 回溯, 剪枝, remain, DFS 元描述：通过 LeetCode 39 建立组合型回溯加剪枝模板，理解可重复选取、remain 语义与排序后的安全剪枝。 A — Algorithm（题目与算法） 题目还原 给定一个无重复元素的整数数组 candidates 和一个目标整数 target， 找出 candidates 中所有可以使数字和为 target 的不同组合，并以列表形式返回。 你可以无限次选取同一个候选数字。 如果两个组合中某个数字出现次数不同，则它们被视为不同组合。 输入输出 名称 类型 描述 candidates int[] 无重复元素的候选数组 target int 目标和 返回 int[][] 所有和为 target 的不同组合 示例 1 输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 示例 2 输入：candidates = [2,3,5], target = 8 输出：[[2,2,2,2],[2,3,3],[3,5]] 示例 3 输入：candidates = [2], target = 1 输出：[] 约束 1 <= candidates.length <= 30 2 <= candidates[i] <= 40 candidates 中所有元素互不相同 1 <= target <= 40 官方保证满足条件的不同组合数少于 150 目标读者 已经做过 78. 子集，现在准备学习“带目标约束”的回溯写法 知道回溯大概长什么样，但一碰到“数字可重复选取”就容易写错边界的学习者 想把这题真正写成模板，而不是只记住 dfs(i, remain - x) 这一行的开发者 背景 / 动机 39. 组合总和 很适合作为回溯第二阶段的训练题，因为它让你同时处理三件事： ...