罗罗编程学习记录
本页内容 展开查看

02.6.2.2 排列类

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.6 回溯与递归 / 02.6.2 经典回溯题型

02.6.2.2-001 全排列 I(LC 46)怎么回溯?

一句话结论

用 used 数组标记已选位置,每层从 0 枚举未用元素加入路径,路径长度等于 n 收集;递归后撤销 used 与路径;无重复元素共 n! 个排列。

概念解释

  • 排列:顺序不同算不同。
  • used:防止同位置重复入路径。

原理流程

  1. 遍历所有位置。
  2. 未用则标记加入。
  3. 长度达标收集,返回撤销。

代码 / 示例

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] 区分同层同支。

原理流程

  1. 排序。
  2. 未用且非同层重复才选。
  3. 递归撤销。

代码 / 示例

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 之后段升序反转;找不到下降点说明已是最大排列,整体反转。

概念解释

  • 字典序:下一个更大的排列。
  • 下降点:可增大的最右位置。

原理流程

  1. 找最右 i 满足 a[i]<a[i+1]。
  2. 右侧找最小大于 a[i] 交换。
  3. 反转 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,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)!。

原理流程

  1. 判断题目是否区分顺序。
  2. 无序用 start。
  3. 有序用 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。

原理流程

  1. 转成可索引序列。
  2. used 标记位置。
  3. 收集时按类型构造结果。

代码 / 示例

// 字符串: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! 排列。

概念解释

  • 阶乘分组:每位候选对应一组排列。
  • 康托:商定位元素,余数定位组内。

原理流程

  1. 维护未选元素有序列表。
  2. 每组大小 (n-1-i)!。
  3. 商选元素,余数更新 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 不同位置。
  • 去重:同层同值一次。

原理流程

  1. 字符排序。
  2. used 标记位置。
  3. 同层重复跳过。

代码 / 示例

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,候选可重复选取。

概念解释

  • 不重复:位置消耗一次。
  • 可重排列:元素可多次出现。

原理流程

  1. 判断题目是否允许重复元素。
  2. 不重复用 used。
  3. 可重则每层全候选枚举。

代码 / 示例

// 不重复:if (used[i]) continue;
// 可重排列:无 used,每层枚举全部候选

常见误区

  • 误区:可重排列也加 used;正解:会漏解。
  • 误区:不重复排列不加 used;正解:同一元素会重复入路径。

追问

  • Q:可重排列复杂度? A:mⁿ,m 为候选种类。
  • Q:密码锁类属于哪种? A:可重排列。

02.6.2.2-010 排列怎么按前缀合法性剪枝?

一句话结论

若题目对相邻元素或前缀有约束(如相邻值差、优美排列),在加入元素前判断当前前缀是否仍合法,不合法则跳过该分支;比走完整个排列再校验省分支。

概念解释

  • 前缀约束:中途即可判定非法。
  • 提前终止:不合法分支不再深入。

原理流程

  1. 明确前缀合法条件。
  2. 选元素前校验与已有路径关系。
  3. 非法 continue。

代码 / 示例

if (!valid(path, nums[i])) continue;

常见误区

  • 误区:生成完整排列再过滤;正解:前缀非法应提前剪。
  • 误区:约束只看新元素不看相邻;正解:按题目关系校验。

追问

  • Q:剪枝条件安全吗? A:前缀非法则扩展后仍非法,可安全剔除。
  • Q:哪些排列题有前缀约束? A:优美排列、相邻差限制、排列还原。

02.6.2.2-011 优美排列(LC 526)怎么做?

一句话结论

位置 1~n,要求第 i 位元素能被 i 整除或 i 能被元素整除;回溯按位置填数,used 标记元素,填前校验整除关系;达标计数。

概念解释

  • 约束:位置与元素整除。
  • 状态:已填位置、已用元素。

原理流程

  1. 按位置递归。
  2. 枚举未用元素校验整除。
  3. 填满计数。

代码 / 示例

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,只计数时不必存路径;撤销与加入成对。

概念解释

  • 路径容器:当前序列。
  • 结果:路径快照。

原理流程

  1. 选中加入路径。
  2. 递归子层。
  3. 收集副本后撤销。

代码 / 示例

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 个排列即逆展开;两者都依赖阶乘与有序剩余列表。

概念解释

  • 正展开:排列 → 排名。
  • 逆展开:排名 → 排列。

原理流程

  1. 每位统计后面更小元素个数。
  2. 乘阶乘累加得排名。
  3. 逆展开按商选元素。

代码 / 示例

排名 = Σ (后方更小元素个数) · (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。

原理流程

  1. 第一层 n 选,逐层递减。
  2. 解数 n!。
  3. 乘单解 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,每层从全部候选枚举,按题目长度终止;如密码、重复填充序列;注意与“候选含重复值但位置唯一”区分。

概念解释

  • 可重用:每层候选全集。
  • 长度:固定位数。

原理流程

  1. 不标记位置消耗。
  2. 每层枚举全部候选。
  3. 达长度收集。

代码 / 示例

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 布尔数组。

原理流程

  1. 位表示已选位置。
  2. 未选位加入路径。
  3. 递归后恢复位。

代码 / 示例

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] 同层判据;排列保留顺序,组合固定方向。

概念解释

  • 组合:方向去重。
  • 排列:值去重,顺序保留。

原理流程

  1. 排序前提一致。
  2. 组合层起点 start。
  3. 排列层全枚举 + 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,返回交换回来;叶子收集数组副本;省掉路径容器。

概念解释

  • 原地交换:当前位与候选位互换。
  • 撤销:交换复原。

原理流程

  1. 固定下标 i。
  2. 枚举 j≥i 交换。
  3. 递归后换回。

代码 / 示例

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;撤销发生在收集之后,否则副本会被清空。

概念解释

  • 复用现场:递归中可变。
  • 快照:收集时点复制。

原理流程

  1. 到达叶子。
  2. 复制当前序列。
  3. 副本入结果再撤销。

代码 / 示例

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 与路径。
  • 去重:排序与判据。
  • 收集:快照拷贝。

原理流程

  1. 小用例跑通无重复排列。
  2. 加重复元素验证去重。
  3. 检查撤销与拷贝。

代码 / 示例

排查:used 标记 / 排序 / 同层判据 / 撤销成对 / 结果拷贝 / 前缀剪枝

常见误区

  • 误区:只用无重复用例验证;正解:必须含重复元素用例。
  • 误区:排列结果乱序不影响;正解:顺序是排列语义的一部分。

追问

  • Q:结果多解重复先查什么? A:排序与同层去重判据。
  • Q:结果缺解先查什么? A:used 是否误置、候选枚举范围。