知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# used 数组 vs startIndex — 一篇讲透本质 ## 先说结论 ``` 问你 "排列" → used 数组 问你 "组合/子集/切割" → startIndex ``` 但这只是表面规则。真正的本质是一个问题:**你选过的元素,后面还能不能再选?** ## 本质:谁来帮你"避免重复" 回溯就是在一棵决策树上穷举。每一层你要做一个选择,问题是:这一层的选择列表是什么? ``` 排列:每一层都可以选数组中的任何元素(只要没被用过) 组合:每一层只能选当前位置之后的元素(不能回头选) ``` 这就是 used 和 startIndex 的全部区别。它们解决的是同一个问题的两种不同场景。 ## 用一个生活例子彻底搞懂 假设有三个人:小明、小红、小刚。 ### 场景一:排队(排列) 三个人排成一队,有几种排法? ``` 第 1 个位置:可以选 小明、小红、小刚(3 个人都可以) 第 2 个位置:可以选 剩下的 2 个人 第 3 个位置:只剩 1 个人 关键:每个位置都要"从头扫描所有人",只是跳过已经站好的人 → 需要 used 数组记录"谁已经站好了" ``` ```java for (int i = 0; i < nums.length; i++) { // 每次从 0 开始 if (used[i]) continue; // 跳过已选的 // ... } ``` ### 场景二:选代表(组合) 三个人中选 2 个当代表,有几种选法? ``` {小明, 小红} 和 {小红, 小明} 是同一组代表 所以选了小明之后,只能从小明后面的人里选 → 不能回头选,用 startIndex 控制起点 ``` ```java for (int i = startIndex; i < nums.length; i++) { // 从 startIndex 开始 // 下一层从 i+1 开始,不回头 backtrack(nums, i + 1, path); } ``` ## 核心区别图解 ``` 数组 [1, 2, 3] ═══ 排列(used 数组)═══ 每一层都从头开始选,用 used 跳过已选的: 第 1 层选择列表:[1, 2, 3] ← 从 i=0 开始 第 2 层选择列表:[_, 2, 3] ← 从 i=0 开始,跳过 used 第 3 层选择列表:[_, _, 3] ← 从 i=0 开始,跳过 used [1,2] 和 [2,1] 是不同的排列 → 都会被生成 ═══ 组合(startIndex)═══ 每一层只能往后选,不回头: 第 1 层选择列表:[1, 2, 3] ← startIndex=0 第 2 层选择列表: [2, 3] ← startIndex=1(选了1之后) 第 3 层选择列表: [3] ← startIndex=2(选了2之后) [1,2] 会被生成,[2,1] 不会 → 天然去重 ``` ## 决策树对比 ``` 排列 [1,2,3] 的决策树: 组合 [1,2,3] 选 2 个的决策树: [] [] / | \ / | \ [1] [2] [3] [1] [2] [3] /\ /\ /\ /\ | [12][13][21][23][31][32] [12][13] [23] | | | | | | [123]... ... 只往后选,不回头 所以 [21] [31] [32] 不会出现 每层都从头选,只跳过 used 所以 [12] 和 [21] 都会出现 ``` ## 判断用哪个的决策流程 ``` 问自己一个问题:[1,2] 和 [2,1] 在这道题里是同一个答案吗? 是同一个答案(无序)→ 组合/子集 → startIndex 不是同一个答案(有序)→ 排列 → used 数组 ``` 更具体的判断: ``` 题目问"排列" / "全排列" / "顺序不同算不同" → used 数组 → for 从 0 开始 题目问"组合" / "子集" / "不考虑顺序" / "切割方案" → startIndex → for 从 startIndex 开始 → 递归时传 i+1(不可重复选)或 i(可重复选) ``` ## 五道题对号入座 ``` 题目 有序? 用什么 for 起点 递归传参 全排列 [1,2,3] 有序 used[] i=0 不需要 startIndex 子集 [1,2,3] 无序 startIndex i=start i+1 组合总和(可重复选) 无序 startIndex i=start i(可重复) 组合总和 II(不可重复选) 无序 startIndex i=start i+1 电话号码字母组合 N/A index 每层不同 index+1 ``` ## 那"去重"呢? used 和 startIndex 解决的是"不同位置的元素不要重复选"。 但如果数组本身有重复元素(比如 [1,1,2]),还需要额外的去重逻辑: ```java // 排序 + 同层跳过 Arrays.sort(nums); if (i > startIndex && nums[i] == nums[i-1]) continue; // 组合去重 if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; // 排列去重 ``` 这是另一个维度的问题: - used / startIndex → 解决"同一个位置的元素不要选两次" - 排序 + 跳过 → 解决"不同位置但值相同的元素,在同一层不要都选" ``` [1a, 1b, 2] 的子集 没有去重:[1a], [1b], [1a,1b], [1a,2], [1b,2], [1a,1b,2] ↑ 和 [1a] 重复 去重后: [1], [1,1], [1,2], [1,1,2] 去重条件:i > startIndex && nums[i] == nums[i-1] 含义:在同一层循环中,如果当前值和前一个值相同,跳过 (第一个 1 已经探索过了,第二个 1 再探索只会产生重复结果) ``` ## 总结成一张表 ``` ┌──────────────┬──────────────┬──────────────────────────┐ │ 场景 │ 机制 │ 本质 │ ├──────────────┼──────────────┼──────────────────────────┤ │ 排列(有序) │ used 数组 │ 每层从头选,跳过已选的 │ │ 组合(无序) │ startIndex │ 每层只往后选,不回头 │ │ 可重复选 │ 递归传 i │ 下一层还能选当前元素 │ │ 不可重复选 │ 递归传 i+1 │ 下一层从下一个元素开始 │ │ 数组有重复值 │ 排序+同层跳过 │ 同一层不选相同值的元素 │ └──────────────┴──────────────┴──────────────────────────┘ ``` ## 最后用一句话记住 > **排列关心顺序,所以每次从头选,用 used 记住谁选过了。** > **组合不关心顺序,所以只往后选,用 startIndex 保证不回头。** 就这么简单。所有的回溯题,先判断"有序还是无序",答案就出来了。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入