知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - 回溯模板与套路总结 ## 什么是回溯 回溯就是暴力搜索的优雅写法。本质是在一棵决策树上做深度优先遍历,走不通就退回来换条路。 生活例子:走迷宫。走到死胡同就退回上一个路口,换一条路继续走。 ``` 回溯三步曲: 1. 做选择(往路径里加一个元素) 2. 递归(继续往下探索) 3. 撤销选择(把刚才加的元素拿掉,回到上一步的状态) ``` ## 万能模板 ```java void backtrack(路径, 选择列表) { if (满足结束条件) { 收集结果; return; } for (选择 : 选择列表) { 做选择; // 把选择加入路径 backtrack(路径, 选择列表); // 递归 撤销选择; // 把选择从路径中移除 } } ``` 就这么个框架,所有回溯题都是往里面填空。 ## 用排列问题理解模板 给你 `[1, 2, 3]`,列出所有排列。 ``` 决策树: [] / | \ [1] [2] [3] ← 第 1 层:选第 1 个数 / \ / \ / \ [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] ← 第 2 层:选第 2 个数 | | | | | | [1,2,3] ... ... ... ... [3,2,1] ← 第 3 层:选第 3 个数 ``` 每个叶子节点就是一个完整的排列。回溯就是遍历这棵树的过程。 ## 回溯的本质:穷举 + 剪枝 ``` 穷举:把所有可能的组合都试一遍 剪枝:提前排除不可能的分支,减少无效搜索 没有剪枝的回溯 = 暴力穷举 有剪枝的回溯 = 聪明的穷举 ``` ## 三类经典问题 ``` 1. 排列问题:有顺序,[1,2] 和 [2,1] 是不同的 → 每次从头开始选,用 used 数组标记已选的 2. 组合/子集问题:无顺序,[1,2] 和 [2,1] 是相同的 → 用 startIndex 控制起点,只往后选,避免重复 3. 切割问题:在字符串的不同位置切一刀 → 本质也是组合问题,切割点就是选择 ``` ## 去重的两种场景 ### 场景一:数组有重复元素,结果不能重复 ``` 输入 [1, 1, 2],求子集 不去重:[1], [1], [1,1], [1,2], [1,2], [1,1,2] ← 有重复 去重后:[1], [1,1], [1,2], [1,1,2] 方法:先排序,同一层中跳过重复元素 if (i > startIndex && nums[i] == nums[i-1]) continue; ``` ### 场景二:同一个元素不能重复使用 ``` 排列问题:每个元素只能用一次 → used[i] = true 标记已使用 组合问题:每个元素只能用一次 → startIndex = i + 1,从下一个开始选 组合问题:每个元素可以重复使用 → startIndex = i,从当前位置继续选 ``` ## 时间复杂度 ``` 排列:O(n! × n) 子集:O(2^n × n) 组合:O(C(n,k) × k) 回溯的时间复杂度通常是指数级的,这是穷举的代价 剪枝能减少常数,但不改变量级 ``` ## 一句话总结 回溯 = for 循环里面套递归,递归前做选择,递归后撤销选择。排列用 used 数组,组合用 startIndex。 --- 下一篇:[02 - 全排列](./02-permutations.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入