回溯

副标题 / 摘要 这题表面上像字符串题，实质上是一个非常标准的固定层数回溯模型：第 k 层只处理第 k 个数字，从其映射字母里选一个，直到路径长度等于输入长度。 预计阅读时长：10~12 分钟 标签：Hot100、回溯、字符串、DFS SEO 关键词：Letter Combinations of a Phone Number, 电话号码的字母组合, 回溯, DFS 元描述：用 LeetCode 17 建立固定层数 DFS 模板，理解字符映射、路径长度终止与多语言实现。 目标读者 已经掌握 78 / 46，准备看另一类回溯树形态的学习者 想把“每层处理一个位置”这种 DFS 模型固定下来的开发者 需要做编码扩展、短串生成、候选串组合的工程师 背景 / 动机 这题和子集、排列都不太一样。 子集题：每层决定“要不要继续选后面的元素” 排列题：每层决定“当前位置放哪个未使用元素” 本题：每层对应一个固定数字位置，只能从该数字映射的字母中选一个 因此它非常适合训练“固定深度 DFS”： 递归层数由输入长度决定 每一层的候选集由当前字符直接决定 路径长度等于输入长度时结束 这类模型在字典枚举、编码扩展、模板字符串生成中很常见。 核心概念 数字映射表：2 -> abc, 3 -> def, …, 9 -> wxyz 固定层数 DFS：第 index 层只处理 digits[index] 叶子条件：index == len(digits) 时得到一个完整答案 路径构建：每层向路径追加一个字符，返回时撤销 A — Algorithm（题目与算法） 题目还原 给定一个仅由数字 2 到 9 组成的字符串 digits，返回它能表示的所有字母组合。 答案顺序不限。数字与字母的映射与电话按键一致，1 不对应任何字母。 ...

副标题 / 摘要 如果说子集题教你“组合型回溯”的骨架，那么全排列题教你的就是“状态型回溯”的核心：当前位置要选一个还没用过的元素，直到路径长度等于 n 才收集答案。 预计阅读时长：10~12 分钟 标签：Hot100、回溯、全排列、DFS SEO 关键词：Permutations, 全排列, 回溯, used, DFS 元描述：通过 LeetCode 46 固定排列型回溯模板，重点理解 used[]、叶子收集与多语言实现。 目标读者 已经做完 78. 子集，准备进入排列型回溯的学习者 会写递归，但状态恢复经常出错的开发者 需要枚举任务执行顺序、测试顺序或操作序列的工程师 背景 / 动机 排列问题和组合问题最本质的区别是： 组合只关心“选了哪些元素” 排列还关心“这些元素出现的顺序” 所以在全排列里，[1,2,3] 和 [1,3,2] 是两个不同答案。 这意味着你不能再靠 startIndex 只向后看，而必须显式记录“哪些元素已经用过”。 LeetCode 46 的价值就在这里：它把“状态恢复”这件事讲得非常干净。 核心概念 path：当前构造中的排列 used[i]：nums[i] 是否已经被当前路径使用 叶子收集答案：只有当路径长度等于 nums.length 时，才得到一个完整排列 状态撤销：递归返回时同时撤销 path 和 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 中所有整数互不相同 C — Concepts（核心思想） 从子集题到全排列题，模板哪里变了 78. 子集 的关键是 startIndex，因为组合不关心顺序。 但全排列不同，每一层都可以从“所有还没用过的元素”里选一个，所以： ...

副标题 / 摘要 子集是 Hot100 回溯专题里最适合打地基的一题。真正要固定下来的不是“把答案都列出来”，而是 path、startIndex 和“每个节点都是答案”这三个核心不变式。 预计阅读时长：10~12 分钟 标签：Hot100、回溯、子集、DFS SEO 关键词：Subsets, 子集, 回溯, startIndex, 幂集 元描述：用 LeetCode 78 子集建立最稳定的回溯模板，含工程场景、复杂度分析与多语言实现。 目标读者 刚进入 Hot100 回溯专题、想先把模板打稳的学习者 能写 DFS，但还没真正理解“组合”和“排列”区别的开发者 希望把枚举思路迁移到配置组合、策略试跑场景的工程师 背景 / 动机 “列出所有可能组合”在工程里并不少见。 比如功能开关组合试跑、权限策略候选集生成、前端筛选项预设等，本质上都在做“从若干候选元素里列出所有选择结果”。 这类问题最容易犯的错有两个： 把组合写成排列，导致重复答案 把“什么时候收集答案”放错位置，导致漏解 LeetCode 78 的价值就在于：它约束足够简单，没有重复元素，也不要求复杂剪枝，适合你先把回溯树的骨架搭稳。 核心概念 path：当前递归路径上已经选中的元素 startIndex：下一层从哪里开始选，保证组合不会倒序重复 前序收集答案：子集题里，每个节点本身就是一个合法答案 回溯撤销：递归返回后，要把刚加入 path 的元素弹出 A — Algorithm（题目与算法） 题目还原 给定一个元素互不相同的整数数组 nums，返回它的所有可能子集。 结果中不能包含重复子集，返回顺序不限。 输入输出 名称 类型 描述 nums int[] 元素互不相同的整数数组 返回 int[][] 所有可能的子集 示例 1 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2 输入：nums = [0] 输出：[[],[0]] 提示 1 <= nums.length <= 10 -10 <= nums[i] <= 10 nums 中所有元素互不相同 C — Concepts（核心思想） 为什么它是回溯入门题 这题没有“目标和”、没有“判重数组”、也没有棋盘边界。 你只需要想清楚一件事： ...

副标题 / 摘要 组合总和是回溯专题里第一道真正把“组合模板 + 目标约束 + 剪枝”揉在一起的题。你要学会的不只是枚举，而是怎样用排序和剩余值 remain 把搜索树收紧。 预计阅读时长：12~15 分钟 标签：Hot100、回溯、组合、剪枝 SEO 关键词：Combination Sum, 组合总和, 回溯, 剪枝, DFS 元描述：通过 LeetCode 39 建立组合型回溯加剪枝模板，理解可重复选取、排序与 remain 约束。 目标读者 已经做过 78. 子集，准备把回溯模板升级到“带约束搜索”的学习者 想搞清楚“同一个数可以重复使用”时递归边界怎么写的开发者 需要做资源打包、预算组合、规格拼装类组合搜索的工程师 背景 / 动机 这题是很多人真正开始理解“回溯不是暴力乱搜”的分水岭。 因为它同时有三件事： 仍然是组合问题，所以要保持顺序无关 候选数字可以重复使用 目标和 target 给了你天然剪枝条件 如果你只会硬搜，代码虽然也许能过，但模板不稳定。 而一旦你把“排序 + remain + 从 i 开始递归”的逻辑想清楚，这一类题都会顺很多。 核心概念 path：当前正在尝试的一组组合 remain：当前还差多少才能凑到目标值 从 i 继续递归：表示当前数字可以重复使用 排序剪枝：若 candidates[i] > remain，后面的数更大，可直接停止 A — Algorithm（题目与算法） 题目还原 给定一个无重复元素的整数数组 candidates 和一个目标值 target， 找出所有和为 target 的不同组合。 ...