回溯算法专题从试错穷举到剪枝与笛卡尔积优化的 LeetCode 解题方法论【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode回溯是深度优先搜索DFS中的一种经典技巧也是 LeetCode 中「求所有解」「求可行方案集合」这类题型的核心武器。本文以本仓库 thinkings/backtrack.md 专题为骨架系统讲解回溯的思想本质、算法流程与通用模板并结合仓库内 78. 子集、46. 全排列、39. 组合总和、842. 将数组拆分成斐波那契序列 等真题深入剖析剪枝技巧与「笛卡尔积 记忆化递归」的高级优化路径。读完本文你将掌握一套可以直接套用的回溯解题公式并理解何时需要在路径上记录结果、何时需要把结果放进返回值。什么是回溯走不通就回头的试错算法回溯法采用试错trial and error的思想它尝试分步去解决一个问题在分步解决问题的过程中当它通过尝试发现现有的分步答案不能得到有效的、正确的解答时它将取消上一步甚至是上几步的计算再通过其他的可能分步解答再次尝试寻找问题的答案。通俗地讲回溯就是走不通就回头的算法。需要特别强调的是回溯的本质是穷举所有可能。尽管有时候可以通过剪枝去除一些根本不可能是答案的分支但从本质上讲回溯仍然是一种暴力枚举算法。这一点决定了回溯题目的复杂度通常是指数级如 $O(2^N)$、$O(N!)$也决定了剪枝与优化在这类题目中举足轻重的地位。回溯的树形结构抽象N 叉树上的搜索回溯法可以抽象为树形结构并且是一棵高度有限的 N 叉树。回溯法解决的问题本质上都是在集合中查找子集其中集合的大小决定了树的分叉数N递归的深度构成了树的高度。以求数组[1, 2, 3]的子集为例整个搜索过程可以组织成一颗从空集出发、逐层选择元素的搜索树第一层分别选择1、2、3第二层在已选元素之后继续向后选择从而穷举出全部子集。这里有一个值得注意的实现细节for循环用来枚举分割点选择点。事实上区间 DP 分割区间时的做法与之类似——都是在一个区间内枚举从哪里切开这体现了不同算法范式之间相通的思想。结果集记录在节点上还是叶子上子集类问题与全排列类问题在何时把结果加入结果集上存在关键差异子集问题如 78. 子集在递归树的每一个节点都执行一次加入结果集的操作。以[1, 2, 3]为例节点上的路径就是结果灰色节点加入结果集的是[1]再向下深入一层加入的是[1, 2]另一条分支上加入的是[2, 3]以此类推一共得到六个子集[1]、[1, 2]、[1, 2, 3]、[2]、[2, 3]、[3]再加上空集即完整幂集。全排列问题如 46. 全排列在叶子节点才把完整路径加入结果集因为排列要求选满所有元素才算一个答案。这些都属于细节层面的差异。先把回溯 树形搜索 走到尽头记录结果的思想掌握扎实再去学习具体题目的细节会事半功倍。算法流程四个步骤回溯的通用算法流程可以概括为以下四步构造空间树把问题的所有可能状态组织成一棵搜索树N 叉树。进行遍历用递归DFS在这棵树上进行深度优先遍历。遇到边界条件即回头一旦不再满足继续向下搜索的条件就停止向下搜索转而搜索另一条链。达到目标条件输出结果当满足目标条件如路径长度达到要求、和等于目标值时记录并输出结果。算法模板回溯的骨架代码下面是本仓库 thinkings/backtrack.md 给出的通用伪代码模板。它囊括了回溯的四个关键动作判断终止 → 标记访问 → 递归展开 → 撤销状态const visited {} function dfs(i) { if (满足特定条件{ // 返回结果 or 退出搜索空间 } visited[i] true // 将当前状态标为已搜索 dosomething(i) // 对i做一些操作 for (根据i能到达的下个状态j) { if (!visited[j]) { // 如果状态j没有被搜索过 dfs(j) } } undo(i) // 恢复i }对照仓库中的多语言实现可以更直观地理解这个模板的每一部分。以 78. 子集 的 JavaScript 实现为例function backtrack(list, tempList, nums, start) { list.push([...tempList]); // 每个节点都加入结果集区别于全排列 for (let i start; i nums.length; i) { tempList.push(nums[i]); // 做选择dosomething backtrack(list, tempList, nums, i 1); // 递归进入下一层start 右移避免重复组合 tempList.pop(); // 撤销选择undo } } var subsets function (nums) { const list []; backtrack(list, [], nums, 0); return list; };46. 全排列 则展示了模板在叶子节点收集结果 防止重复选取上的变体用tempList.includes(nums[i])或哈希集合判断当前元素是否已被选取tempList.length nums.length时在叶子节点收集结果。仓库中还给出了一种交换式的排列写法Python 的permute3/ C 实现通过swap(nums[start], nums[i])就地交换来生成排列回溯时再交换回来省去了 visited 数组void dfs(vectorint nums, int start) { if (start nums.size() - 1) { ans.push_back(nums); return; } for (int i start; i nums.size(); i) { swap(nums[i], nums[start]); dfs(nums, start 1); swap(nums[i], nums[start]); } }从源码结构看这两个变体的共性在于都严格遵循选择 → 递归 → 撤销的回溯三段式差异只体现在结果收集时机与去重手段上。剪枝回溯的第二个考点回溯题目的另一个核心考点是剪枝——通过恰当地剪枝可以有效减少搜索时间。例如本仓库作者曾通过剪枝操作将「石子游戏 V」的运行时间从 900 多毫秒优化到 500 多毫秒。剪枝在每道题中的具体技巧各不相同但有一条基本原则避免递归那些根本不可能是答案的分支。实战案例842. 将数组拆分成斐波那契序列题目要求给定一个数字字符串S如S 123456579将它拆分成斐波那契式序列[123, 456, 579]。形式化定义如下序列F是非负整数列表且每个元素满足0 F[i] 2^31 - 132 位有符号整数F.length 3对所有0 i F.length - 2满足F[i] F[i1] F[i2]拆分出的每个数字块不能以零开头除非这个块就是数字0本身。几个代表性示例输入输出说明123456579[123, 456, 579]基本用例11235813[1, 1, 2, 3, 5, 8, 13]标准斐波那契序列112358130[]无法拆分0123[]数字块不能以零开头01非法1101111[110, 1, 111][11, 0, 11, 11]同样可接受数据范围1 S.length 200字符串只含数字。由于长度可达 200如果不进行合适地剪枝很容易超时。直接套回溯模板配合以下四个剪枝操作即可通过class Solution: def splitIntoFibonacci(self, S: str) - List[int]: def backtrack(start, path): # 剪枝1斐波那契校验 —— 一旦新加入的数不满足前两数之和立即终止该分支 if len(path) 2 and path[-1] ! path[-2] path[-3]: return [] if start len(S): if len(path) 2: return path return [] cur 0 ans [] # 枚举分割点 for i in range(start, len(S)): # 剪枝2前导零 —— 除数字 0 本身外块不能以 0 开头 if i start and S[start] 0: return [] cur cur * 10 int(S[i]) # 剪枝332 位整数上界 —— 超过 2^31 - 1 直接放弃 if cur 2**31 - 1: return [] path.append(cur) ans backtrack(i 1, path) # 剪枝4提前返回 —— 已找到合法序列长度 2就不再继续尝试 if len(ans) 2: return ans path.pop() return ans return backtrack(0, [])四个剪枝分别对应四类根本不可能成为答案的分支斐波那契性质剪枝剪枝 1一旦路径中出现F[i] F[i1] ! F[i2]后续无论怎么拆都不可能合法立刻终止前导零剪枝剪枝 2i start S[start] 0时当前数字块以零开头且长度大于 1非法数值范围剪枝剪枝 3累加过程中一旦cur 2^31 - 1越界的块全部作废提前成功剪枝剪枝 4题目只要求返回任意一组合法序列找到即停止避免无谓的后续穷举。这个案例是理解剪枝不是玄学而是把题目约束翻译成终止条件的最佳范本——剪枝 1、2、3 来自题目约束本身剪枝 4 来自题目任意一组的松约束。剪枝的另一个常见形态重复元素去重对于包含重复元素的输入剪枝常表现为排序 相邻相等跳过。以 90. 子集 II 为例[1, 2, 2]的两个2没有区别交换两者的位置只能算一种情况。仓库给出的处理方式是先排序再规定一种针对相邻且相等情况的取数逻辑——i start nums[i] nums[i - 1]时跳过i为当前索引start为当前层起始索引从而保证无论多少个相邻的相同数字只有一种取法。同样的思路也出现在 40. 组合总和 II、47. 全排列 II 中。笛卡尔积把结果放进返回值避免回溯状态对于一部分回溯题目我们还可以采用笛卡尔积的方式把结果保存在返回值中而不是路径path中。这样做有两个直接收益避免了显式的回溯撤销状态无需 undo由于结果保存在返回值中可以借助记忆化递归memoization消除重复子问题进而优化为动态规划形式。这类问题不同于子集和全排列——它们的组合是有规律的我们可以使用笛卡尔积公式将两个或更多子集联合起来。仓库中的代表题目包括140. 单词拆分 II401. 二进制手表816. 模糊坐标实例140. 单词拆分 II 的笛卡尔积优化140. 单词拆分 II 要求给定非空字符串s和单词字典wordDict在字符串中增加空格构建句子返回所有可能的句子单词可重复使用字典无重复单词。暴力回溯版本Pythonclass Solution: def wordBreak(self, s: str, wordDict: List[str]) - List[str]: ans [] n len(s) def backtrack(temp, start): if start n: ans.append(temp[1:]) for i in range(start, n): if s[start:i 1] in wordDict: backtrack(temp s[start:i 1], i 1) backtrack(, 0) return ans这个版本复杂度为 $O(2^N)$在诸如s长度达 151大量a拼接、字典包含a到aaaaaaaaaa的用例上会超时。如果是在真实面试中一定要先问清楚数据范围——这是本题给我们的重要提醒。优化思路在于观察重叠子问题当我们 DFS 探到底部例如触及hi时就知道了s[-2:]可能组成的所有可能就是[hi, h, i]再往上探到worldhi时其可能结果就是当前探测到的单词与上一步所有可能的笛卡尔积。多个分支共享同一后缀时这个计算会被重复执行。因此把结果放进返回值并加记忆化即可消除重复计算class Solution: def wordBreak(self, s: str, wordDict: List[str]) - List[str]: n len(s) lru_cache(None) def backtrack(start): ans [] if start n: ans.append() for i in range(start, n): if s[start:i 1] in wordDict: if start 0: temp s[start:i 1] else: temp s[start:i 1] ps backtrack(i 1) for p in ps: ans.append(temp p) return ans return backtrack(0)改造后复杂度由 $O(2^N)$ 降为 $O(N^2)$其中 N 为字符串长度。这种记忆化递归的方式与 DP 思想一模一样可以进一步改写为动态规划形式——这正是仓库文档结果放返回值 → 记忆化 → 动态规划优化链路的完整呈现。经典题目清单回溯解题的练习路径回溯模板的可迁移性极强本仓库沉淀了一批经典练习题建议按子集 → 组合 → 排列 → 分割 → 棋盘的梯度依次攻克题型类别题目核心差异点子集78. 子集每个节点收集结果start右移防重复子集含重复90. 子集 II排序 i start nums[i] nums[i-1]去重组合39. 组合总和元素可重复选取递归传i而非i 1组合含重复40. 组合总和 II每个数字只能用一次 去重排列46. 全排列叶子节点收集visited/ swap 防重复排列含重复47. 全排列 II排序 同层跳过重复元素棋盘/约束52. N 皇后 II行列/对角线冲突判断即剪枝树与路径113. 路径总和 II二叉树上的回溯 路径累加字符串分割131. 分割回文串枚举分割点 回文校验剪枝组合优化1255. 得分最高的单词集合回溯 计数/得分约束剪枝其中 39. 组合总和 与 40. 组合总和 II 恰好构成一组对比前者允许重复选取元素递归参数为i后者每个元素只能使用一次递归参数为i 1两者都以排序作为剪枝前置。这组对照是理解递归参数ivsi 1这一核心细节的最佳素材。总结回溯的本质就是暴力枚举所有可能其搜索空间是一棵高度有限的 N 叉树集合大小决定分叉数、递归深度决定树高。必须重视状态撤销由于回溯的结果集通常记录在回溯树的路径上如果不进行撤销操作undo/pop回溯后状态不正确会导致结果差异因此需要在递归从底部往上冒泡时撤销状态。拷贝路径可免撤销但换空间如果你每次递归都拷贝一份数据就不需要撤销状态但空间复杂度会相应增加。例如 46. 全排列 的 Pythonpermute2实现就通过pre_list.copy()与left_nums.copy()避免了显式 undo。剪枝是回溯的另一大考点把题目约束数值范围、前导零、斐波那契性质、重复元素等翻译成终止条件可以成倍压缩搜索空间。高级优化方向是笛卡尔积把结果放进返回值、配合记忆化递归可以消除重复子问题并平滑过渡到动态规划140. 单词拆分 II 是这一链路的完整示范。掌握树形抽象 模板三段式 剪枝约束翻译 结果位置选择这四个要点再配合本仓库 thinkings/backtrack.md 与经典题目清单进行刻意练习回溯这一题型将不再是难点。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 回溯算法专题：从试错穷举到剪枝与笛卡尔积优化的 LeetCode 解题方法论
回溯算法专题从试错穷举到剪枝与笛卡尔积优化的 LeetCode 解题方法论【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode回溯是深度优先搜索DFS中的一种经典技巧也是 LeetCode 中「求所有解」「求可行方案集合」这类题型的核心武器。本文以本仓库 thinkings/backtrack.md 专题为骨架系统讲解回溯的思想本质、算法流程与通用模板并结合仓库内 78. 子集、46. 全排列、39. 组合总和、842. 将数组拆分成斐波那契序列 等真题深入剖析剪枝技巧与「笛卡尔积 记忆化递归」的高级优化路径。读完本文你将掌握一套可以直接套用的回溯解题公式并理解何时需要在路径上记录结果、何时需要把结果放进返回值。什么是回溯走不通就回头的试错算法回溯法采用试错trial and error的思想它尝试分步去解决一个问题在分步解决问题的过程中当它通过尝试发现现有的分步答案不能得到有效的、正确的解答时它将取消上一步甚至是上几步的计算再通过其他的可能分步解答再次尝试寻找问题的答案。通俗地讲回溯就是走不通就回头的算法。需要特别强调的是回溯的本质是穷举所有可能。尽管有时候可以通过剪枝去除一些根本不可能是答案的分支但从本质上讲回溯仍然是一种暴力枚举算法。这一点决定了回溯题目的复杂度通常是指数级如 $O(2^N)$、$O(N!)$也决定了剪枝与优化在这类题目中举足轻重的地位。回溯的树形结构抽象N 叉树上的搜索回溯法可以抽象为树形结构并且是一棵高度有限的 N 叉树。回溯法解决的问题本质上都是在集合中查找子集其中集合的大小决定了树的分叉数N递归的深度构成了树的高度。以求数组[1, 2, 3]的子集为例整个搜索过程可以组织成一颗从空集出发、逐层选择元素的搜索树第一层分别选择1、2、3第二层在已选元素之后继续向后选择从而穷举出全部子集。这里有一个值得注意的实现细节for循环用来枚举分割点选择点。事实上区间 DP 分割区间时的做法与之类似——都是在一个区间内枚举从哪里切开这体现了不同算法范式之间相通的思想。结果集记录在节点上还是叶子上子集类问题与全排列类问题在何时把结果加入结果集上存在关键差异子集问题如 78. 子集在递归树的每一个节点都执行一次加入结果集的操作。以[1, 2, 3]为例节点上的路径就是结果灰色节点加入结果集的是[1]再向下深入一层加入的是[1, 2]另一条分支上加入的是[2, 3]以此类推一共得到六个子集[1]、[1, 2]、[1, 2, 3]、[2]、[2, 3]、[3]再加上空集即完整幂集。全排列问题如 46. 全排列在叶子节点才把完整路径加入结果集因为排列要求选满所有元素才算一个答案。这些都属于细节层面的差异。先把回溯 树形搜索 走到尽头记录结果的思想掌握扎实再去学习具体题目的细节会事半功倍。算法流程四个步骤回溯的通用算法流程可以概括为以下四步构造空间树把问题的所有可能状态组织成一棵搜索树N 叉树。进行遍历用递归DFS在这棵树上进行深度优先遍历。遇到边界条件即回头一旦不再满足继续向下搜索的条件就停止向下搜索转而搜索另一条链。达到目标条件输出结果当满足目标条件如路径长度达到要求、和等于目标值时记录并输出结果。算法模板回溯的骨架代码下面是本仓库 thinkings/backtrack.md 给出的通用伪代码模板。它囊括了回溯的四个关键动作判断终止 → 标记访问 → 递归展开 → 撤销状态const visited {} function dfs(i) { if (满足特定条件{ // 返回结果 or 退出搜索空间 } visited[i] true // 将当前状态标为已搜索 dosomething(i) // 对i做一些操作 for (根据i能到达的下个状态j) { if (!visited[j]) { // 如果状态j没有被搜索过 dfs(j) } } undo(i) // 恢复i }对照仓库中的多语言实现可以更直观地理解这个模板的每一部分。以 78. 子集 的 JavaScript 实现为例function backtrack(list, tempList, nums, start) { list.push([...tempList]); // 每个节点都加入结果集区别于全排列 for (let i start; i nums.length; i) { tempList.push(nums[i]); // 做选择dosomething backtrack(list, tempList, nums, i 1); // 递归进入下一层start 右移避免重复组合 tempList.pop(); // 撤销选择undo } } var subsets function (nums) { const list []; backtrack(list, [], nums, 0); return list; };46. 全排列 则展示了模板在叶子节点收集结果 防止重复选取上的变体用tempList.includes(nums[i])或哈希集合判断当前元素是否已被选取tempList.length nums.length时在叶子节点收集结果。仓库中还给出了一种交换式的排列写法Python 的permute3/ C 实现通过swap(nums[start], nums[i])就地交换来生成排列回溯时再交换回来省去了 visited 数组void dfs(vectorint nums, int start) { if (start nums.size() - 1) { ans.push_back(nums); return; } for (int i start; i nums.size(); i) { swap(nums[i], nums[start]); dfs(nums, start 1); swap(nums[i], nums[start]); } }从源码结构看这两个变体的共性在于都严格遵循选择 → 递归 → 撤销的回溯三段式差异只体现在结果收集时机与去重手段上。剪枝回溯的第二个考点回溯题目的另一个核心考点是剪枝——通过恰当地剪枝可以有效减少搜索时间。例如本仓库作者曾通过剪枝操作将「石子游戏 V」的运行时间从 900 多毫秒优化到 500 多毫秒。剪枝在每道题中的具体技巧各不相同但有一条基本原则避免递归那些根本不可能是答案的分支。实战案例842. 将数组拆分成斐波那契序列题目要求给定一个数字字符串S如S 123456579将它拆分成斐波那契式序列[123, 456, 579]。形式化定义如下序列F是非负整数列表且每个元素满足0 F[i] 2^31 - 132 位有符号整数F.length 3对所有0 i F.length - 2满足F[i] F[i1] F[i2]拆分出的每个数字块不能以零开头除非这个块就是数字0本身。几个代表性示例输入输出说明123456579[123, 456, 579]基本用例11235813[1, 1, 2, 3, 5, 8, 13]标准斐波那契序列112358130[]无法拆分0123[]数字块不能以零开头01非法1101111[110, 1, 111][11, 0, 11, 11]同样可接受数据范围1 S.length 200字符串只含数字。由于长度可达 200如果不进行合适地剪枝很容易超时。直接套回溯模板配合以下四个剪枝操作即可通过class Solution: def splitIntoFibonacci(self, S: str) - List[int]: def backtrack(start, path): # 剪枝1斐波那契校验 —— 一旦新加入的数不满足前两数之和立即终止该分支 if len(path) 2 and path[-1] ! path[-2] path[-3]: return [] if start len(S): if len(path) 2: return path return [] cur 0 ans [] # 枚举分割点 for i in range(start, len(S)): # 剪枝2前导零 —— 除数字 0 本身外块不能以 0 开头 if i start and S[start] 0: return [] cur cur * 10 int(S[i]) # 剪枝332 位整数上界 —— 超过 2^31 - 1 直接放弃 if cur 2**31 - 1: return [] path.append(cur) ans backtrack(i 1, path) # 剪枝4提前返回 —— 已找到合法序列长度 2就不再继续尝试 if len(ans) 2: return ans path.pop() return ans return backtrack(0, [])四个剪枝分别对应四类根本不可能成为答案的分支斐波那契性质剪枝剪枝 1一旦路径中出现F[i] F[i1] ! F[i2]后续无论怎么拆都不可能合法立刻终止前导零剪枝剪枝 2i start S[start] 0时当前数字块以零开头且长度大于 1非法数值范围剪枝剪枝 3累加过程中一旦cur 2^31 - 1越界的块全部作废提前成功剪枝剪枝 4题目只要求返回任意一组合法序列找到即停止避免无谓的后续穷举。这个案例是理解剪枝不是玄学而是把题目约束翻译成终止条件的最佳范本——剪枝 1、2、3 来自题目约束本身剪枝 4 来自题目任意一组的松约束。剪枝的另一个常见形态重复元素去重对于包含重复元素的输入剪枝常表现为排序 相邻相等跳过。以 90. 子集 II 为例[1, 2, 2]的两个2没有区别交换两者的位置只能算一种情况。仓库给出的处理方式是先排序再规定一种针对相邻且相等情况的取数逻辑——i start nums[i] nums[i - 1]时跳过i为当前索引start为当前层起始索引从而保证无论多少个相邻的相同数字只有一种取法。同样的思路也出现在 40. 组合总和 II、47. 全排列 II 中。笛卡尔积把结果放进返回值避免回溯状态对于一部分回溯题目我们还可以采用笛卡尔积的方式把结果保存在返回值中而不是路径path中。这样做有两个直接收益避免了显式的回溯撤销状态无需 undo由于结果保存在返回值中可以借助记忆化递归memoization消除重复子问题进而优化为动态规划形式。这类问题不同于子集和全排列——它们的组合是有规律的我们可以使用笛卡尔积公式将两个或更多子集联合起来。仓库中的代表题目包括140. 单词拆分 II401. 二进制手表816. 模糊坐标实例140. 单词拆分 II 的笛卡尔积优化140. 单词拆分 II 要求给定非空字符串s和单词字典wordDict在字符串中增加空格构建句子返回所有可能的句子单词可重复使用字典无重复单词。暴力回溯版本Pythonclass Solution: def wordBreak(self, s: str, wordDict: List[str]) - List[str]: ans [] n len(s) def backtrack(temp, start): if start n: ans.append(temp[1:]) for i in range(start, n): if s[start:i 1] in wordDict: backtrack(temp s[start:i 1], i 1) backtrack(, 0) return ans这个版本复杂度为 $O(2^N)$在诸如s长度达 151大量a拼接、字典包含a到aaaaaaaaaa的用例上会超时。如果是在真实面试中一定要先问清楚数据范围——这是本题给我们的重要提醒。优化思路在于观察重叠子问题当我们 DFS 探到底部例如触及hi时就知道了s[-2:]可能组成的所有可能就是[hi, h, i]再往上探到worldhi时其可能结果就是当前探测到的单词与上一步所有可能的笛卡尔积。多个分支共享同一后缀时这个计算会被重复执行。因此把结果放进返回值并加记忆化即可消除重复计算class Solution: def wordBreak(self, s: str, wordDict: List[str]) - List[str]: n len(s) lru_cache(None) def backtrack(start): ans [] if start n: ans.append() for i in range(start, n): if s[start:i 1] in wordDict: if start 0: temp s[start:i 1] else: temp s[start:i 1] ps backtrack(i 1) for p in ps: ans.append(temp p) return ans return backtrack(0)改造后复杂度由 $O(2^N)$ 降为 $O(N^2)$其中 N 为字符串长度。这种记忆化递归的方式与 DP 思想一模一样可以进一步改写为动态规划形式——这正是仓库文档结果放返回值 → 记忆化 → 动态规划优化链路的完整呈现。经典题目清单回溯解题的练习路径回溯模板的可迁移性极强本仓库沉淀了一批经典练习题建议按子集 → 组合 → 排列 → 分割 → 棋盘的梯度依次攻克题型类别题目核心差异点子集78. 子集每个节点收集结果start右移防重复子集含重复90. 子集 II排序 i start nums[i] nums[i-1]去重组合39. 组合总和元素可重复选取递归传i而非i 1组合含重复40. 组合总和 II每个数字只能用一次 去重排列46. 全排列叶子节点收集visited/ swap 防重复排列含重复47. 全排列 II排序 同层跳过重复元素棋盘/约束52. N 皇后 II行列/对角线冲突判断即剪枝树与路径113. 路径总和 II二叉树上的回溯 路径累加字符串分割131. 分割回文串枚举分割点 回文校验剪枝组合优化1255. 得分最高的单词集合回溯 计数/得分约束剪枝其中 39. 组合总和 与 40. 组合总和 II 恰好构成一组对比前者允许重复选取元素递归参数为i后者每个元素只能使用一次递归参数为i 1两者都以排序作为剪枝前置。这组对照是理解递归参数ivsi 1这一核心细节的最佳素材。总结回溯的本质就是暴力枚举所有可能其搜索空间是一棵高度有限的 N 叉树集合大小决定分叉数、递归深度决定树高。必须重视状态撤销由于回溯的结果集通常记录在回溯树的路径上如果不进行撤销操作undo/pop回溯后状态不正确会导致结果差异因此需要在递归从底部往上冒泡时撤销状态。拷贝路径可免撤销但换空间如果你每次递归都拷贝一份数据就不需要撤销状态但空间复杂度会相应增加。例如 46. 全排列 的 Pythonpermute2实现就通过pre_list.copy()与left_nums.copy()避免了显式 undo。剪枝是回溯的另一大考点把题目约束数值范围、前导零、斐波那契性质、重复元素等翻译成终止条件可以成倍压缩搜索空间。高级优化方向是笛卡尔积把结果放进返回值、配合记忆化递归可以消除重复子问题并平滑过渡到动态规划140. 单词拆分 II 是这一链路的完整示范。掌握树形抽象 模板三段式 剪枝约束翻译 结果位置选择这四个要点再配合本仓库 thinkings/backtrack.md 与经典题目清单进行刻意练习回溯这一题型将不再是难点。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考