回溯

题目要求 输入输出 输入：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] 会从不同路径重复出现。 先写最小骨架。它只保留两个状态： ...

题目要求 输入输出 输入：nums，长度 1 <= nums.length <= 10 元素范围：-10 <= nums[i] <= 10 nums 可能有重复元素 输出：返回所有不重复子集 顺序：结果顺序不限，但同一个值序列的子集只能出现一次 示例 输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]] 这篇只用 Python，从一个能跑但浪费的版本，一步一步过渡到排序 + 层内去重。 从 [1,2,2] 的重复分支开始 最小能暴露问题的例子是： nums = [1,2,2] 如果直接照搬 78. 子集 的模板，搜索树里会出现两条不同分支： 选择下标 1 的 2 -> [2] 选择下标 2 的 2 -> [2] 这两个分支路径不同，但值序列相同，最终答案重复。 所以这题真正新增的问题不是“会不会回溯”，而是： 怎样跳过重复分支，同时保留 [2,2] 这种合法答案？ Step 1：先复用 78 的状态，看看哪里会坏 当前部分答案仍然需要 path；当前层仍然需要 start 控制只能往右选。 先写出 78 的核心版本： def dfs(start: int) -> None: res.append(path.copy()) for i in range(start, len(nums)): path.append(nums[i]) dfs(i + 1) path.pop() 这个版本在 nums 全部互不相同时是正确的。 ...

51. N 皇后 最适合用“代码一步一步长出来”的方式学，而不是直接看一个已经想好的模板答案。 这篇教程只保留教学主线：先从最小例子暴露冲突，再写最小 DFS 骨架，先得到第一版正确解，然后一步步优化到列 / 对角线状态版。 题目 n 皇后问题要求在一个 n x n 的棋盘上放置 n 个皇后，使得任意两个皇后都不能互相攻击。 给定整数 n，返回所有不同的放置方案。 每个方案都用一个字符串数组表示，其中： 'Q' 表示皇后 '.' 表示空位 示例 1 输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 示例 2 输入：n = 1 输出：[["Q"]] 约束 1 <= n <= 9 一步一步把代码逼出来 Step 1：先看最小能暴露冲突的例子 先只问一个很具体的问题： 放下一个皇后以后，到底麻烦在哪里？ 看 n = 4。 假设第 0 行把皇后放在第 1 列。 那么后面的行就不再是“随便找一个空格”了，而是立刻多出三类限制： 第 1 列不能再放 一条左上到右下的对角线不能再放 一条右上到左下的对角线不能再放 这个最小例子已经说明了问题的本质： 我们要按某种固定顺序放置皇后 每做一个选择，都会封锁后面的若干位置 这一版还没有代码。 现在这一版能做到： 看清楚题目的冲突结构 但它还缺： ...

副标题 / 摘要 131. 分割回文串 的难点不是递归本身，而是两个问题要同时想清楚：当前切到了哪里，以及一个候选片段是不是回文。把这两件事拆开，你就能得到“回溯枚举 + 回文表预处理”的稳定写法。 预计阅读时长：15~18 分钟 标签：Hot100、回溯、字符串、回文、DP SEO 关键词：Palindrome Partitioning, 分割回文串, 回溯, 回文预处理, DP 元描述：通过 LeetCode 131 理解字符串分割型回溯与回文区间预处理，掌握“先判合法片段，再递归切后缀”的题目模型。 A — Algorithm（题目与算法） 题目还原 给定一个字符串 s，请把它切分成若干个子串，使得每个子串都是回文串，并返回所有可能的切分方案。 输入输出 名称 类型 描述 s string 只包含小写英文字母的字符串 返回 string[][] 所有合法的回文切分方案 示例 1 输入：s = "aab" 输出：[["a","a","b"],["aa","b"]] 示例 2 输入：s = "a" 输出：[["a"]] 约束 1 <= s.length <= 16 s 仅由小写英文字母组成 目标读者 已经学过 78/90 这类数组回溯，准备进入“字符串切分型回溯”的学习者 会写递归，但总把“切分位置”和“合法性检查”搅在一起的开发者 想掌握“先预处理合法区间，再枚举切分”的工程迁移套路的读者 背景 / 动机 这题非常适合帮你建立一种更通用的模型： 先判断哪些区间是合法片段，再递归地把整个串切完。 如果你只是把它看成“回文题”，容易只盯着 isPalindrome()。 但如果你把它看成“字符串分割题”，就会更清楚它的结构： ...

副标题 / 摘要 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. 组合总和 很适合作为回溯第二阶段的训练题，因为它让你同时处理三件事： ...