教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载导读本文以 LogicStack-LeetCode 仓库公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列中「回溯算法」专题索引Index/回溯算法.md为核心骨架系统讲解回溯算法DFS Backtracking的判定方法、通用框架、去重策略与剪枝技巧。通过 17 道经典题17. 电话号码的字母组合、37. 解数独、39. 组合总和、40. 组合总和 II、90. 子集 II、93. 复原 IP 地址、131. 分割回文串、301. 删除无效的括号、剑指 Offer 38. 字符串的排列 等读者可以完整掌握回溯算法的选题判断、递归函数设计、去重与剪枝方法以及在不同题型中的落地应用。一、回溯算法是什么DFS 的「决策-递归-撤销」循环回溯算法本质上是深度优先搜索DFS的一种应用形态。它的核心思想是把问题的求解过程抽象为一棵「决策树」树的每一层代表一次决策树的每一条根到叶子的路径代表一种完整方案搜索时沿着某条路径深入当发现当前路径不可能得到合法解时退回上一层撤销上一次决策换一条分支继续深入。在 LogicStack-LeetCode 的系列题解中这一思想被反复强调。以 17. 电话号码的字母组合中等 为例题解给出的完整实现如下class Solution { MapString, String[] map new HashMap(){{ put(2, new String[]{a, b, c}); put(3, new String[]{d, e, f}); put(4, new String[]{g, h, i}); put(5, new String[]{j, k, l}); put(6, new String[]{m, n, o}); put(7, new String[]{p, q, r, s}); put(8, new String[]{t, u, v}); put(9, new String[]{w, x, y, z}); }}; public ListString letterCombinations(String ds) { int n ds.length(); ListString ans new ArrayList(); if (n 0) return ans; StringBuilder sb new StringBuilder(); dfs(ds, 0, n, sb, ans); return ans; } void dfs(String ds, int i, int n, StringBuilder sb, ListString ans) { if (i n) { ans.add(sb.toString()); return; } String key ds.substring(i, i 1); String[] all map.get(key); for (String item : all) { sb.append(item); dfs(ds, i 1, n, sb, ans); sb.deleteCharAt(sb.length() - 1); // 关键撤销决策 } } }这段代码完整展示了回溯三要素决策对当前位的数字ds[i]枚举其映射的每个字母item递归将字母加入当前结果sb后深入下一层处理i 1撤销sb.deleteCharAt(sb.length() - 1)在返回上层前把上一次的添加回滚保证同一层循环中多个分支共享同一个状态。复杂度方面n代表数字串长度一个数字最多对应 4 个字符因此时间复杂度为 O(4ⁿ)空间复杂度为 O(4ⁿ)答案本身占用的空间。二、如何快速判断一道题该用回溯两条硬性标准回溯算法的应用场景是有迹可循的。在 39. 组合总和中等 与 40. 组合总和 II中等 的题解中给出了判断「是否应该使用 DFS 回溯爆搜」的两条标准判断维度具体标准说明求解目标求的是所有的方案而不是方案数由于要求所有方案难以做特殊优化只能枚举。候选解法有动态规划、记忆化搜索、DFS 回溯数据范围通常不会太大只有几十动态规划 / 记忆化搜索擅长低重复枚举数据范围可到 10⁴~10⁵而 DFS 回溯通常被限制在30 以内以 39 题为例candidates.length限制在1 n 30且要求输出所有和为target的组合因此直接采用 DFS 回溯。题解代码如下class Solution { public ListListInteger combinationSum(int[] cs, int t) { ListListInteger ans new ArrayList(); ListInteger cur new ArrayList(); dfs(cs, t, 0, ans, cur); return ans; } /** * cs: 原数组从该数组进行选数 * t: 还剩多少值需要凑成。起始值为 target代表还没选择任何数当 t 0代表选择的数凑成了 target * u: 当前决策到 cs[] 中的第几位 * ans: 最终结果集 * cur: 当前结果集 */ void dfs(int[] cs, int t, int u, ListListInteger ans, ListInteger cur) { if (t 0) { ans.add(new ArrayList(cur)); return; } if (u cs.length || t 0) return; // 枚举 cs[u] 的使用次数 for (int i 0; cs[u] * i t; i) { dfs(cs, t - cs[u] * i, u 1, ans, cur); cur.add(cs[u]); } // 进行回溯。注意回溯总是将数组的最后一位弹出 for (int i 0; cs[u] * i t; i) { cur.remove(cur.size() - 1); } } }这里有一个非常实用的编码细节回溯时总是将当前结果集cur的最后一位弹出cur.remove(cur.size() - 1)。由于递归是先深入后返回返回时cur的末尾恰好是本次决策添加的元素所以统一弹出末尾即可完成状态回滚。三、回溯的核心三问决策什么、状态传什么、何时终止纵观索引表中 17 道题每道题的 DFS 函数都可以用「三问」来设计3.1 决策什么递归树的每一层做什么组合类39、40、698. 划分为k个相等的子集决策「当前数组元素选或不选」或「选几次」子集类90. 子集 II决策「当前位置元素是否加入子集」分割类131、93决策「从当前位置切一刀的右端点在哪」排列类剑指 Offer 38决策「目标串当前位置填入哪个字符」棋盘 / 网格类37、1219. 黄金矿工、797. 所有可能的路径、212. 单词搜索 II决策「下一步走到哪个格子 / 填入哪个数字」。3.2 状态传什么递归函数的参数典型的状态参数包括u / idx当前决策到原数组 / 字符串的哪一位cur当前累积的中间方案组合、子集、分割片段、路径等约束类参数如 39/40 题中的t还剩多少值需要凑成、301 题中的score括号得分、剑指 Offer 38 中的vis字符是否已使用。3.3 何时终止递归出口方案完整如 17 题i n、39 题t 0、剑指 Offer 38 题u n不可能再有合法解剪枝如 39 题u cs.length || t 0、93 题cur.size() 4、301 题score 0 || score max。四、去重回溯中最容易翻车的环节索引表中有多道题要求「解集不能包含重复的组合 / 子集 / 排列」去重策略是回溯的核心考点。系列题解给出了两条主流路线4.1 路线一排序 Set 去重简单直观在 40. 组合总和 II 中由于每个数字只能使用一次直接决策「用或不用」即可但为了确保[1,2,1]与[1,1,2]这类方案在去重时被识别为相同需要先对数组排序保证所有合法方案中数值从小到大排列再配合Set去重class Solution { public ListListInteger combinationSum2(int[] cs, int t) { Arrays.sort(cs); SetListInteger ans new HashSet(); ListInteger cur new ArrayList(); dfs(cs, t, 0, ans, cur); return new ArrayList(ans); } void dfs(int[] cs, int t, int u, SetListInteger ans, ListInteger cur) { if (t 0) { ans.add(new ArrayList(cur)); return; } if (u cs.length || t 0) return; // 使用 cs[u] cur.add(cs[u]); dfs(cs, t - cs[u], u 1, ans, cur); // 进行回溯 cur.remove(cur.size() - 1); // 不使用 cs[u] dfs(cs, t, u 1, ans, cur); } }同样90. 子集 II 的「回溯解法Set」也是先Arrays.sort(nums)然后对每个位置决策「选 / 不选」最终用HashSet收口。此方案时间复杂度为排序 O(n log n) 爆搜 O(n × 2ⁿ)。4.2 路线二按「相同数值被选择的个数」决策不用 Set子集 II 的题解进一步指出Set 的 O(1) 只是均摊意义且会引入额外开销。去重的本质是避免「相同的元素、不同的决策方案产生同样的结果」——例如对[1,1,1]只选第一个和只选第三个会得到两个[1]。正确的做法是不要按「某个下标是否被选择」决策而是找到某个数值的连续一段按「该数值被选择的个数0 个、1 个、2 个 …」进行决策。这样[1,1,1]只会因为「1 被选择一次」产生一个[1]方案天然不会重复class Solution { public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); ListListInteger ans new ArrayList(); ListInteger cur new ArrayList(); dfs(nums, 0, cur, ans); return ans; } void dfs(int[] nums, int u, ListInteger cur, ListListInteger ans) { int n nums.length; if (n u) { ans.add(new ArrayList(cur)); return; } // 记录当前位置是什么数值令数值为 t并找出数值为 t 的连续一段 int t nums[u]; int last u; while (last n nums[last] nums[u]) last; // 不选当前位置的元素直接跳到 last 往下决策 dfs(nums, last, cur, ans); // 决策选择不同个数的 t 的情况选择 1 个、2 个、3 个 ... k 个 for (int i u; i last; i) { cur.add(nums[i]); dfs(nums, last, cur, ans); } // 回溯对数值 t 的选择 for (int i u; i last; i) { cur.remove(cur.size() - 1); } } }4.3 排列问题的排序去重剑指 Offer 38. 字符串的排列中等 同样提供了两种去重方式。其中「排序去重」的做法值得单独强调先对原字符串排序然后确保相同字符传入同一目标位置的动作只发生一次。在决策目标字符串第u个位置时对cs[i-1] cs[i]的情况跳过并利用同一目标位置会「回溯」的特性增加!vis[i - 1]判断。这样对形如...xxx...的原字符串使用字符x决策目标位置的动作只会发生一次一模一样的分支不会在递归树中展开多次。其本质是对递归树中「当前形成部分结果相同、剩余字符集合也相同」的状态节点进行跳过。五、剪枝让爆搜从「指数爆炸」变为「可接受」回溯必须配合剪枝才能实用。系列题解中出现了多类剪枝范式5.1 分数约束剪枝括号问题删除无效的括号困难 是剪枝思想的集大成者。题解定义左括号得分 1、右括号得分 -1则合法方案必然满足最终得分为 0搜索过程中任意前缀得分不为负右括号数量不能超过左括号数量。同时预处理出爆搜过程的最大得分max min(左括号数量, 右括号数量)。搜索时对每个字符分三种情况左括号(若score 1 max则可选「添加」或「不添加」右括号)若score - 1 0则可选「添加」或「不添加」普通字符直接添加。并在入口处直接剪掉非法状态score 0 || score maxclass Solution { SetString set new HashSet(); int n, max, len; String s; public ListString removeInvalidParentheses(String _s) { s _s; n s.length(); int l 0, r 0; for (char c : s.toCharArray()) { if (c () l; else if (c )) r; } max Math.min(l, r); dfs(0, , 0); return new ArrayList(set); } void dfs(int u, String cur, int score) { if (score 0 || score max) return; if (u n) { if (score 0 cur.length() len) { if (cur.length() len) set.clear(); len cur.length(); set.add(cur); } return; } char c s.charAt(u); if (c () { dfs(u 1, cur String.valueOf(c), score 1); dfs(u 1, cur, score); } else if (c )) { dfs(u 1, cur String.valueOf(c), score - 1); dfs(u 1, cur, score); } else { dfs(u 1, cur String.valueOf(c), score); } } }该题还给出了第二层剪枝通过预处理算出「必须删除的左括号数l和右括号数r」直接得到最终len n - l - r搜索时一旦l、r归零且当前长度等于len即记录答案避免搜索结束后再比较长度。该解法在仓库中同时提供了 Java、C、Python 三个版本适合对照学习。5.2 合法性剪枝复原 IP 地址复原 IP 地址中等 在枚举分割点时逐层剪枝若cs[idx] 0且当前段长度超过 1前导零直接break若当前段数值t 255直接break若cur.size() 4直接返回IP 只有 4 段。class Solution { ListString ans new ArrayList(); char[] cs; public ListString restoreIpAddresses(String s) { cs s.toCharArray(); dfs(0, cs.length, new ArrayList()); return ans; } void dfs(int idx, int n, ListInteger cur) { if (cur.size() 4) return; if (idx n) { if (cur.size() 4) { StringBuilder sb new StringBuilder(); for (int i 0; i 4; i) sb.append(cur.get(i)).append(.); ans.add(sb.substring(0, sb.length() - 1)); } } else { for (int i idx; i n; i) { int t 0; for (int j idx; j i; j) t t * 10 (cs[j] - 0); if (cs[idx] 0 i ! idx) break; if (t 255) break; cur.add(t); dfs(i 1, n, cur); cur.remove(cur.size() - 1); } } } }5.3 固定规模剪枝棋盘类解数独困难 指出棋盘类回溯有一个显著特征数据范围固定且很小。数独棋盘固定为 9×9N 皇后问题的 N 一般不超过 13。这类题对每个空格尝试填入 1~9若当前候选数字在行、列、宫三个维度均未出现则填入并递归否则回溯。由于棋盘固定其时间复杂度可视作常数级 O(1)极端情况下最多枚举 9×9×9 729 次。class Solution { boolean[][] row new boolean[9][9]; boolean[][] col new boolean[9][9]; boolean[][][] cell new boolean[3][3][9]; public void solveSudoku(char[][] board) { for (int i 0; i 9; i) { for (int j 0; j 9; j) { if (board[i][j] ! .) { int t board[i][j] - 1; row[i][t] col[j][t] cell[i / 3][j / 3][t] true; } } } dfs(board, 0, 0); } boolean dfs(char[][] board, int x, int y) { if (y 9) return dfs(board, x 1, 0); if (x 9) return true; if (board[x][y] ! .) return dfs(board, x, y 1); for (int i 0; i 9; i) { if (!row[x][i] !col[y][i] !cell[x / 3][y / 3][i]) { board[x][y] (char)(i 1); row[x][i] col[y][i] cell[x / 3][y / 3][i] true; if (dfs(board, x, y 1)) { break; } else { board[x][y] .; row[x][i] col[y][i] cell[x / 3][y / 3][i] false; } } } return board[x][y] ! .; } }注意这里用的是剪枝 提前返回的写法找到第一组合法解就回溯到根并结束dfs返回true适合「保证唯一解」的数独场景而 301 题等「输出所有方案」的题目则不允许提前返回。六、分割类问题的经典套路131 与 93分割类问题是回溯的另一大分支核心思想在 131. 分割回文串中等 中讲得最透彻凡求所有方案的题基本上没有优化空间只能爆搜。关键在于爆搜每个回文串的起点——如果有连续的一段是回文串再对剩下的连续一段继续爆搜。因为任意子串最终必然能分割成若干回文串最坏情况下每个字符单独成段所以每次往下爆搜只需保证自身连续一段是回文串即可。以abababa为例从起点a开始发现a是回文串分割后对bababa爆搜发现aba是回文串分割后对baba爆搜依此类推。只需要以首个字符为起点枚举所有以其开头的回文串方案加入集合再对剩余部分继续爆搜就能覆盖以任意字符作为回文串起点的分割效果。由于爆搜复杂度为 O(2ⁿ)题解用区间 DP 预处理出f[i][j]代表[i, j]是否为回文串避免每次用双指针线性扫描状态转移f[i][j] (s[i] s[j]) f[i1][j-1]长度为 2 时退化为s[i] s[j]长度为 1 时为 true遍历顺序f[i][j]依赖f[i1][j-1]因此左端点i从大到小、右端点j从小到大。这与 Index/回文串问题.md 中回文串预处理的知识点形成呼应也是「回溯 预处理加速」的典型组合。同一套路还延伸到了 93. 复原 IP 地址分割点枚举 数值合法性校验和 95. 不同的二叉搜索树 II枚举根节点分割左右子树。七、网格 / 图上爆搜797 与 1219回溯同样适用于图与网格所有可能的路径中等在有向无环图上枚举从源点到终点的所有路径DFS 每深入一层就追加一个节点返回时弹出黄金矿工中等网格四方向探索每格价值大于 0 时才能进入进入后标记访问、累加收益、递归、回溯时恢复标记求全局最大收益单词搜索 II困难在网格中匹配多个单词可结合字典树Trie做前缀剪枝可对照 Index/字典树.md。这类题共同的实现要点是**「访问标记的进与出」必须成对出现**进入格子前标记visited递归返回后立即撤销否则不同路径会互相干扰。八、专题索引全貌17 道题一览索引表 Index/回溯算法.md 共收录 17 道题按题型与推荐指数整理如下题号题目难度核心考点17电话号码的字母组合中等映射决策 标准回溯模板37解数独困难棋盘回溯 行/列/宫三重约束39组合总和中等元素可重复选 枚举使用次数40组合总和 II中等元素不可重复 Set 去重90子集 II中等子集去重Set / 按个数决策93复原 IP 地址中等分割点枚举 合法性剪枝95不同的二叉搜索树 II中等根节点枚举 左右子树组合131分割回文串中等回文预处理 起点爆搜212单词搜索 II困难网格爆搜 Trie 剪枝301删除无效的括号困难括号得分剪枝 双层剪枝306累加数中等高精度相加 回溯校验698划分为k个相等的子集中等子集划分 可行性剪枝797所有可能的路径中等图路径枚举1219黄金矿工中等网格四方向回溯 访问标记2698求一个整数的惩罚数中等递归枚举 平方串分割判断剑指 Offer 38字符串的排列中等排列去重Set / 排序去重306 / 93 等——高精度、字符串、分割的组合运用题目难度分布上中等题占绝大多数适合作为回溯入门与进阶的练习序列困难题37、212、301集中考察剪枝与数据结构配合。九、复杂度与数据范围的统一认知从系列题解可以总结出回溯算法的通用复杂度画像时间复杂度指数级为主。典型如 17 题 O(4ⁿ)、组合 / 子集类 O(n × 2ⁿ)、301 题 O(n × 2ⁿ)不考虑剪枝时最坏每个位置两种选择。这正是回溯题数据范围被限制在 30 以内甚至更小如 90 题 n ≤ 10、剑指 Offer 38 长度 ≤ 8、131 题 n ≤ 16的根本原因空间复杂度由「方案总数 × 单个方案大小」决定。组合 / 子集类为 O(n × 2ⁿ)每个方案深拷贝入答案括号类与合法方案数呈线性关系 O(n)棋盘类因规模固定为 O(1)。因此实战中判断顺序应为先看是否求所有方案再看数据范围是否在 30 以内两者满足则优先考虑回溯并立刻着手设计剪枝条件。十、总结一份可直接复用的回溯模板综合系列题解可以沉淀出一份通用的回溯代码骨架void dfs(状态参数, int u, 中间结果 cur, 最终答案 ans) { // 1. 终止条件方案完整 → 收集答案注意深拷贝 if (u 终止位置) { ans.add(new ArrayList(cur)); return; } // 2. 剪枝条件不可能合法 → 提前返回 if (非法状态) return; // 3. 枚举本层所有决策 for (每个候选) { // 4. 做出决策添加 / 标记 / 累加 cur.add(候选); // 5. 深入下一层 dfs(状态更新, u 1, cur, ans); // 6. 撤销决策弹出 / 取消标记 / 减回 cur.remove(cur.size() - 1); } }使用要点状态参数最小化只传「决策位置 约束状态 中间结果」越少越不易出错回溯与递归成对添加了什么返回前必须撤销什么弹出末尾、恢复标记、还原得分去重先排序需要 Set 去重时先排序保证方案有序进阶做法是按相同数值的「选择个数」决策剪枝优先分数约束、前导零、越界值、剩余配额等能提前判断就提前return/break答案深拷贝cur是共享的中间容器存入答案时必须new ArrayList(cur)否则后续回溯会污染已存结果。从 Index/回溯算法.md 索引出发按「入门17、39、40→ 进阶90、131、93、剑指 Offer 38、95→ 困难37、301、212、698」的顺序刷完这 17 道题即可系统掌握回溯算法的判定、框架、去重与剪枝全流程。仓库中每道题均提供了完整题解 Markdown如 LeetCode/11-20/17. 电话号码的字母组合中等.md、LeetCode/301-310/301. 删除无效的括号困难.md部分题目如 301 题还同时给出 Java、C、Python 三语言实现适合对照学习与本地调试。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐Hello 算法回溯章节练习详解从状态回退、有序去重到 N 皇后剪枝的完整解题指南Hello 算法回溯章节练习详解从状态回退、有序去重到 N 皇后剪枝的完整解题指南 本篇技术文章基于《Hello 算法》回溯算法章节的练习文档展开完整覆盖原教程文档示例工程教育《Hello 算法》回溯算法实战子集和问题中的位置剪枝与等值元素去重《Hello 算法》回溯算法实战子集和问题中的位置剪枝与等值元素去重 本文基于《Hello 算法》仓库中「回溯算法」一章的子集和问题文档展开系统讲解两个经典教程文档示例工程教育Hello 算法子集和问题的回溯求解——从重复子集剪枝到相等元素剪枝的完整实战解析Hello 算法子集和问题的回溯求解——从重复子集剪枝到相等元素剪枝的完整实战解析 本篇技术指南以《Hello 算法》回溯章节中的子集和问题为核心系统讲解如教程文档示例工程教育上一篇llama.cpp语音合成TTS与语音模型集成下一篇Store数据备份X6图形状态安全策略创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考