02.6.2.2 排列类
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.2 经典回溯题型
02.6.2.2-001 全排列 I(LC 46)怎么回溯?
一句话结论
用 used 数组标记已选位置,每层从 0 枚举未用元素加入路径,路径长度等于 n 收集;递归后撤销 used 与路径;无重复元素共 n! 个排列。
概念解释
- 排列:顺序不同算不同。
- used:防止同位置重复入路径。
原理流程
- 遍历所有位置。
- 未用则标记加入。
- 长度达标收集,返回撤销。
代码 / 示例
void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true; path.add(nums[i]);
dfs(nums, used, path, res);
path.remove(...); used[i] = false;
}
}
常见误区
- 误区:用 start 推进;正解:排列要回头选未用元素,用 used。
- 误区:忘记撤销 used;正解:否则后续分支无法再选该位置。
追问
- Q:复杂度? A:时间 O(n·n!),空间 O(n) 辅助。
- Q:结果为什么拷贝? A:path 复用,需存快照。
02.6.2.2-002 全排列 II 去重(LC 47)怎么做?
一句话结论
排序后用 used 数组;同层遇到相等元素且前一同值未使用则跳过;既挡同值兄弟重复,又保留同支合法选择;其余流程同全排列 I。
概念解释
- 重复值:不同位置同值。
- 判据:
!used[i-1]区分同层同支。
原理流程
- 排序。
- 未用且非同层重复才选。
- 递归撤销。
代码 / 示例
if (used[i]) continue;
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
常见误区
- 误区:去掉 used 判断直接相等跳过;正解:会误杀同支选择。
- 误区:不排序;正解:重复值需相邻才能比较。
追问
- Q:解的数量? A:多重排列数 n!/(各重复阶乘)。
- Q:used[i-1]=true 为什么允许? A:前一同值在祖先路径,属不同位置。
02.6.2.2-003 下一个排列(LC 31)怎么求?
一句话结论
从右往左找首个下降点 a[i]<a[i+1],再从右找首个大于 a[i] 的位置交换,最后把 i 之后段升序反转;找不到下降点说明已是最大排列,整体反转。
概念解释
- 字典序:下一个更大的排列。
- 下降点:可增大的最右位置。
原理流程
- 找最右 i 满足 a[i]<a[i+1]。
- 右侧找最小大于 a[i] 交换。
- 反转 i 之后段为升序。
代码 / 示例
public void nextPermutation(int[] a) {
int i = a.length - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--;
if (i >= 0) {
int j = a.length - 1;
while (a[j] <= a[i]) j--;
swap(a, i, j);
}
reverse(a, i + 1, a.length - 1);
}
常见误区
- 误区:交换后右侧保持原序;正解:右侧需翻转为最小升序。
- 误区:下降点找成最左;正解:要最右可增大点。
追问
- Q:复杂度? A:O(n),空间 O(1)。
- Q:已是最大排列怎么办? A:整体反转为最小排列。
02.6.2.2-004 排列的字典序是什么?
一句话结论
字典序按位置逐位比较,首个不同位上值大者排列更大;下一个排列就是大于当前排列的最小那个;排列可按字典序排成线性序列。
概念解释
- 逐位比较:与字符串字典序同理。
- 后继:紧邻的更大排列。
原理流程
- 从左到右比较位。
- 首位大者整体更大。
- 求后继按下降点规则。
代码 / 图示
[1,2,3] < [1,3,2]:第二位 2<3
常见误区
- 误区:按数值整体大小比较;正解:按位字典序。
- 误区:认为排列顺序无关;正解:排列序列有字典序。
追问
- Q:康托展开作用? A:把排列映射为字典序排名。
- Q:最小/最大排列? A:升序最小,降序最大。
02.6.2.2-005 排列与组合的本质区别是什么?
一句话结论
组合只关心选哪些元素(无序集合),排列关心选出元素的摆放顺序(有序序列);组合用 start 固定方向,排列用 used 枚举全部顺序;同一批元素排列数多于组合数。
概念解释
- 组合:C(n,k)。
- 排列:P(n,k)=n!/(n-k)!。
原理流程
- 判断题目是否区分顺序。
- 无序用 start。
- 有序用 used。
代码 / 示例
组合 [1,2] 一个;排列 [1,2]、[2,1] 两个
常见误区
- 误区:排列也能用 start 去重;正解:start 会禁止回头选,漏掉顺序。
- 误区:组合结果要排所有顺序;正解:组合只存一个代表顺序。
追问
- Q:有序方案计数对应哪种 DP? A:外层容量内层硬币的排列型背包。
- Q:k=n 时排列数? A:n!。
02.6.2.2-006 数字排列与字符串排列写法有何异同?
一句话结论
框架相同:used + 路径 + 撤销;数字按元素值收集,字符串按字符收集;字符串可先转字符数组,重复字符去重条件与数字重复值一致。
概念解释
- 元素类型:int / char。
- 容器:List
/ StringBuilder。
原理流程
- 转成可索引序列。
- used 标记位置。
- 收集时按类型构造结果。
代码 / 示例
// 字符串:StringBuilder 追加/删除
sb.append(c); dfs(...); sb.deleteCharAt(sb.length()-1);
常见误区
- 误区:String 拼接后不撤销;正解:String 不可变无需撤销,StringBuilder 必须回退。
- 误区:字符重复值不去重;正解:同值字符同样排序跳过。
追问
- Q:字符串排列结果存什么? A:String,每个排列一个新串。
- Q:字符数组与字符串转换? A:toCharArray 与 new String(arr)。
02.6.2.2-007 第 k 个排列(LC 60)怎么定位?
一句话结论
用阶乘(康托)定位:每一位有 (n-1)! 个排列,按 k 除以阶乘选出当前位元素,剩余 k 取余数,递归处理剩余元素;避免枚举全部 n! 排列。
概念解释
- 阶乘分组:每位候选对应一组排列。
- 康托:商定位元素,余数定位组内。
原理流程
- 维护未选元素有序列表。
- 每组大小
(n-1-i)!。 - 商选元素,余数更新 k。
代码 / 示例
List<Integer> nums = new ArrayList<>();
for (int i = 1; i <= n; i++) nums.add(i);
int[] fact = new int[n]; fact[0] = 1;
for (int i = 1; i < n; i++) fact[i] = fact[i-1] * i;
k--; // 转 0 基
for (int i = n; i >= 1; i--) {
int idx = k / fact[i - 1];
sb.append(nums.remove(idx));
k %= fact[i - 1];
}
常见误区
- 误区:k 不先减 1;正解:阶乘分组是 0 基,k 要减一。
- 误区:选元素后不从剩余列表移除;正解:已选位不再参与后续。
追问
- Q:复杂度? A:O(n²)(列表删除),空间 O(n)。
- Q:k 越界怎么处理? A:按题意取模或校验。
02.6.2.2-008 含重复字符的字符串全排列怎么去重?
一句话结论
字符排序后同层相邻重复跳过,判据与数字排列一致;!used[i-1] 区分同层同支;结果收集字符串;重复字符只在第一位置展开兄弟分支。
概念解释
- 重复字符:相等 char 不同位置。
- 去重:同层同值一次。
原理流程
- 字符排序。
- used 标记位置。
- 同层重复跳过。
代码 / 示例
if (i > 0 && c[i] == c[i-1] && !used[i-1]) continue;
常见误区
- 误区:字符转字符串后比较;正解:按 char 位置比较更直接。
- 误区:忘记排序字符;正解:重复字符需相邻。
追问
- Q:结果用 Set 兜底可行吗? A:可行但低效,优先搜索层去重。
- Q:重复字符排列数? A:多重排列数。
02.6.2.2-009 排列中元素为什么不能重复进入路径?
一句话结论
每个位置在一个排列中最多出现一次,used 标记已选位置防止同位置再次入路径;若允许重复使用元素(可重排列),则不用 used,候选可重复选取。
概念解释
- 不重复:位置消耗一次。
- 可重排列:元素可多次出现。
原理流程
- 判断题目是否允许重复元素。
- 不重复用 used。
- 可重则每层全候选枚举。
代码 / 示例
// 不重复:if (used[i]) continue;
// 可重排列:无 used,每层枚举全部候选
常见误区
- 误区:可重排列也加 used;正解:会漏解。
- 误区:不重复排列不加 used;正解:同一元素会重复入路径。
追问
- Q:可重排列复杂度? A:mⁿ,m 为候选种类。
- Q:密码锁类属于哪种? A:可重排列。
02.6.2.2-010 排列怎么按前缀合法性剪枝?
一句话结论
若题目对相邻元素或前缀有约束(如相邻值差、优美排列),在加入元素前判断当前前缀是否仍合法,不合法则跳过该分支;比走完整个排列再校验省分支。
概念解释
- 前缀约束:中途即可判定非法。
- 提前终止:不合法分支不再深入。
原理流程
- 明确前缀合法条件。
- 选元素前校验与已有路径关系。
- 非法 continue。
代码 / 示例
if (!valid(path, nums[i])) continue;
常见误区
- 误区:生成完整排列再过滤;正解:前缀非法应提前剪。
- 误区:约束只看新元素不看相邻;正解:按题目关系校验。
追问
- Q:剪枝条件安全吗? A:前缀非法则扩展后仍非法,可安全剔除。
- Q:哪些排列题有前缀约束? A:优美排列、相邻差限制、排列还原。
02.6.2.2-011 优美排列(LC 526)怎么做?
一句话结论
位置 1~n,要求第 i 位元素能被 i 整除或 i 能被元素整除;回溯按位置填数,used 标记元素,填前校验整除关系;达标计数。
概念解释
- 约束:位置与元素整除。
- 状态:已填位置、已用元素。
原理流程
- 按位置递归。
- 枚举未用元素校验整除。
- 填满计数。
代码 / 示例
void dfs(int pos, boolean[] used, int n) {
if (pos > n) { count++; return; }
for (int x = 1; x <= n; x++) {
if (!used[x] && (x % pos == 0 || pos % x == 0)) {
used[x] = true; dfs(pos + 1, used, n); used[x] = false;
}
}
}
常见误区
- 误区:整除方向写反;正解:双向
x%pos==0 || pos%x==0。 - 误区:按元素递归位置;正解:约束在位置上,按位置填更直接。
追问
- Q:复杂度? A:最坏 O(n!),约束剪枝后下降。
- Q:能用记忆化吗? A:已用集合是状态,规模小可掩码缓存。
02.6.2.2-012 排列路径怎么还原与记录?
一句话结论
路径存已选元素(或下标),used 同步标记;到达长度收集路径副本;需要还原具体排列时保留 path,只计数时不必存路径;撤销与加入成对。
概念解释
- 路径容器:当前序列。
- 结果:路径快照。
原理流程
- 选中加入路径。
- 递归子层。
- 收集副本后撤销。
代码 / 示例
path.add(nums[i]);
dfs(...);
res.add(new ArrayList<>(path)); // 叶子收集
path.remove(...);
常见误区
- 误区:计数题也存全部路径;正解:只累加计数省空间。
- 误区:路径存下标输出值;正解:收集时映射为值。
追问
- Q:路径长度什么时候到 n? A:填满所有位置。
- Q:多解共享路径吗? A:复用一条 path,收集时拷贝。
02.6.2.2-013 康托展开与逆展开是什么?
一句话结论
康托展开把排列映射为其字典序排名(小于它的排列数);逆展开由排名反推排列;LC 60 第 k 个排列即逆展开;两者都依赖阶乘与有序剩余列表。
概念解释
- 正展开:排列 → 排名。
- 逆展开:排名 → 排列。
原理流程
- 每位统计后面更小元素个数。
- 乘阶乘累加得排名。
- 逆展开按商选元素。
代码 / 示例
排名 = Σ (后方更小元素个数) · (n-1-i)!
常见误区
- 误区:排名从 1 基不换算;正解:计算用 0 基,输出再 +1。
- 误区:剩余列表未排序;正解:逆展开需有序列表定位商。
追问
- Q:康托展开复杂度? A:O(n²),可用树状数组优化到 O(n log n)。
- Q:有重复元素能直接康托吗? A:需多重排列口径,直接阶乘不适用。
02.6.2.2-014 排列复杂度 n! 怎么估算?
一句话结论
n 个不重复元素全排列 n! 个,每个排列构造/拷贝 O(n),时间 O(n·n!);辅助空间 O(n)(栈、used、path);剪枝与去重减少实际分支,最坏按 n! 估。
概念解释
- 分支:每层剩余元素数递减。
- 阶乘:n×(n-1)×…×1。
原理流程
- 第一层 n 选,逐层递减。
- 解数 n!。
- 乘单解 O(n) 拷贝。
代码 / 示例
n=3:3×2×1=6 个排列
常见误区
- 误区:排列复杂度 O(n²);正解:解数阶乘级。
- 误区:忽略拷贝代价;正解:每解 O(n) 入结果。
追问
- Q:n 较大怎么办? A:n! 爆炸,需数学定位或 DP 计数。
- Q:可重排列复杂度? A:mⁿ。
02.6.2.2-015 可重排列(元素可重复使用)怎么写?
一句话结论
候选元素可多次出现时不使用 used,每层从全部候选枚举,按题目长度终止;如密码、重复填充序列;注意与“候选含重复值但位置唯一”区分。
概念解释
- 可重用:每层候选全集。
- 长度:固定位数。
原理流程
- 不标记位置消耗。
- 每层枚举全部候选。
- 达长度收集。
代码 / 示例
void dfs(int depth, List<Integer> path, int n) {
if (depth == n) { res.add(new ArrayList<>(path)); return; }
for (int x : candidates) {
path.add(x); dfs(depth + 1, path, n); path.remove(...);
}
}
常见误区
- 误区:加 used 导致只能用一次;正解:可重用不标记。
- 误区:候选重复值不处理;正解:候选本身重复仍会产生重复解,需去重。
追问
- Q:复杂度? A:mⁿ,m 候选数。
- Q:与组合总和可重复选区别? A:那是组合无序,这是排列有序。
02.6.2.2-016 排列的状态压缩视角是什么?
一句话结论
已选元素集合可用位掩码表示,mask 第 i 位为 1 表示已选;排列回溯中 mask 替代 used 数组,便于记忆化与位运算判断;n ≤ 20 时可行。
概念解释
- 掩码:整数位集合。
- 替代:used 布尔数组。
原理流程
- 位表示已选位置。
- 未选位加入路径。
- 递归后恢复位。
代码 / 示例
if (((mask >> i) & 1) == 0) {
dfs(mask | (1 << i));
}
常见误区
- 误区:n 很大还用掩码;正解:2ⁿ 状态爆炸,受限规模使用。
- 误区:掩码恢复写成异或不匹配;正解:加入用或,撤销用与非。
追问
- Q:掩码适合计数 DP 吗? A:适合,状压 DP 枚举未选位转移。
- Q:与 used 数组等价吗? A:等价,掩码更紧凑。
02.6.2.2-017 排列去重与组合去重怎么对比?
一句话结论
两者都先排序;组合去重靠 start + 同层相邻跳过,不用 used;排列去重靠 used + !used[i-1] 同层判据;排列保留顺序,组合固定方向。
概念解释
- 组合:方向去重。
- 排列:值去重,顺序保留。
原理流程
- 排序前提一致。
- 组合层起点 start。
- 排列层全枚举 + used。
代码 / 示例
组合:if (i>start && a[i]==a[i-1]) continue;
排列:if (相等 && !used[i-1]) continue;
常见误区
- 误区:把组合去重条件搬到排列;正解:排列需要 used 区分同支。
- 误区:排列用 start;正解:禁止回头选会漏顺序。
追问
- Q:无重复元素排列要去重判断吗? A:不需要,但仍需 used。
- Q:去重后两者解数公式? A:组合 C(n,k),排列多重阶乘比。
02.6.2.2-018 交换法排列(原地 swap 回溯)怎么写?
一句话结论
不维护 path,直接在数组上交换:固定位置 i,枚举 i 之后元素交换到 i,递归 i+1,返回交换回来;叶子收集数组副本;省掉路径容器。
概念解释
- 原地交换:当前位与候选位互换。
- 撤销:交换复原。
原理流程
- 固定下标 i。
- 枚举 j≥i 交换。
- 递归后换回。
代码 / 示例
void dfs(int i, int[] a, List<List<Integer>> res) {
if (i == a.length) { res.add(Arrays.stream(a).boxed().toList()); return; }
for (int j = i; j < a.length; j++) {
swap(a, i, j);
dfs(i + 1, a, res);
swap(a, i, j);
}
}
常见误区
- 误区:交换后不换回;正解:现场必须复原。
- 误区:交换法去重条件复杂;正解:重复值需同层跳过交换。
追问
- Q:交换法优势? A:无 path 容器,原地操作。
- Q:去重怎么加? A:同层重复值跳过交换,或用 Set 层上去重。
02.6.2.2-019 排列结果收集与拷贝要注意什么?
一句话结论
数组/path 复用,叶子收集必须拷贝;交换法收集时复制整个数组;字符串排列收集新 String;撤销发生在收集之后,否则副本会被清空。
概念解释
- 复用现场:递归中可变。
- 快照:收集时点复制。
原理流程
- 到达叶子。
- 复制当前序列。
- 副本入结果再撤销。
代码 / 示例
res.add(new ArrayList<>(path)); // 列表
res.add(Arrays.copyOf(a, n)); // 数组
常见误区
- 误区:存引用导致结果全空;正解:收集快照。
- 误区:二维结构只复制外层;正解:内容逐元素复制。
追问
- Q:String 要拷贝吗? A:不可变,直接存。
- Q:拷贝代价? A:O(n) 每解。
02.6.2.2-020 排列类常见错误有哪些?
一句话结论
高频错误:漏 used 导致重复入位、去重条件误杀同支、未排序比较相邻、收集未拷贝、交换法未复原、前缀约束未提前剪;按 used、排序、撤销、拷贝逐项排查。
概念解释
- 现场:used 与路径。
- 去重:排序与判据。
- 收集:快照拷贝。
原理流程
- 小用例跑通无重复排列。
- 加重复元素验证去重。
- 检查撤销与拷贝。
代码 / 示例
排查:used 标记 / 排序 / 同层判据 / 撤销成对 / 结果拷贝 / 前缀剪枝
常见误区
- 误区:只用无重复用例验证;正解:必须含重复元素用例。
- 误区:排列结果乱序不影响;正解:顺序是排列语义的一部分。
追问
- Q:结果多解重复先查什么? A:排序与同层去重判据。
- Q:结果缺解先查什么? A:used 是否误置、候选枚举范围。