CS-Notes 剑指 Offer 38 题详解：字符串的排列——字典序输出 + 剪枝去重的回溯法

本篇围绕 CS-Notes 剑指 Offer 题解中的第 38 题「字符串的排列」展开：给定一个字符串，按字典序打印出其中字符的所有排列。文中给出该仓库题解的完整 Java 回溯实现，逐行剖析"先排序 + hasUsed 去重剪枝"这一核心设计的正确性，并补充交换法这一替代方案、复杂度分析与边界情况，帮助读者建立可复用于所有全排列类问题的回溯思维框架。

题目定义

在 剑指 Offer 38：字符串的排列 的原始题解中，题目描述为：

输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc，则打印出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

这道题有两个隐含要求，缺一不可：

1. 不重不漏：每个字符（按位置区分）恰好使用一次，枚举出全部 n! 种（无重复字符时）排列；
2. 按字典序输出：结果序列必须有序，且当输入含重复字符时，输出不能出现相同的字符串。

在 CS-Notes 的剑指 Offer 题解目录中，本题被归入「搜索」分类，与矩阵中的路径、机器人的运动范围 同属回溯（Backtracking）这一算法家族的典型应用。

为什么自然建模为回溯

求"所有排列"本质上是一棵决策树：

• 第 1 层：从 n 个字符中任选 1 个放在结果的第 1 位，有 n 种选择；
• 第 2 层：从剩余 n-1 个字符中任选 1 个放在第 2 位；
• ……
• 第 n 层：最后剩 1 个字符，必然落位。

当结果串长度达到 n 时，一条从根到叶子的路径就对应一个完整排列。回溯法的骨架永远是"做选择 → 递归进入下一层 → 撤销选择"，本题的全部技巧都浓缩在如何组织"做选择"这一步——既要跳过已用字符，又要剪掉会产生重复结果的分支。

完整解法：排序 + hasUsed 剪枝去重

下面是原仓库题解中的完整 Java 实现，本文保留其原貌，仅在注释中补充意图：

private ArrayList<String> ret = new ArrayList<>();

public ArrayList<String> Permutation(String str) {
    if (str.length() == 0)
        return ret;                      // 空串边界：直接返回空结果
    char[] chars = str.toCharArray();
    Arrays.sort(chars);                  // 先排序：保证字典序 + 让相同字符相邻
    backtracking(chars, new boolean[chars.length], new StringBuilder());
    return ret;
}

private void backtracking(char[] chars, boolean[] hasUsed, StringBuilder s) {
    if (s.length() == chars.length) {   // 一条路径选满了 n 个字符，收集结果
        ret.add(s.toString());
        return;
    }
    for (int i = 0; i < chars.length; i++) {
        if (hasUsed[i])
            continue;                                        // 剪枝 1：跳过已选字符
        if (i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1]) /* 保证不重复 */
            continue;                                        // 剪枝 2：同层重复字符剪枝
        hasUsed[i] = true;
        s.append(chars[i]);
        backtracking(chars, hasUsed, s);
        s.deleteCharAt(s.length() - 1);
        hasUsed[i] = false;
    }
}

逐点剖析

1. 入口处的两个关键动作

• 空串判断：str.length() == 0 时直接返回空的 ret，避免空输入进入递归造成无意义分支。
• Arrays.sort(chars) 先排序，它同时服务于两个目的：
  • 字典序输出：回溯是"按枚举顺序依次收集结果"的，只要每层循环天然从索引 0 遍历到末尾，且字符数组本身有序，收集到的序列就是字典序递增的，无需对结果再排序；
  • 去重的前提：排序把相同的字符聚拢到相邻位置，"跳过重复分支"才有可检查的局部依据（即下一个要点中的 chars[i] == chars[i-1]）。

2. hasUsed 数组：标记"这一层选了谁"

boolean[] hasUsed 与字符数组等长，hasUsed[i] == true 表示第 i 个字符已经出现在当前路径 s 中。循环开头的 if (hasUsed[i]) continue; 保证同一个字符在一条路径里不会被选两次，从而保证"不重"。

3. 去重剪枝：整道题最核心的三条件

if (i != 0 && chars[i] == chars[i - 1] && !hasUsed[i - 1])
    continue;

这条剪枝解决"同一层决策中，多个相同字符造成完全重复的子树"。以输入 "aab" 为例，排序后数组为 ['a', 'a', 'b']。在第 1 层（s 为空）：

• i = 0 选第一个 a：i == 0，不满足条件，正常进入，展开子树 {a, a, b}、{a, b, a} 两支；
• i = 1 选第二个 a：三个条件同时成立——i != 0、chars[1] == chars[0]（都是 a）、!hasUsed[0]（第一个 a 是上一层选的，回溯时已置回 false）——于是剪掉。因为"第 1 位放 a"这件事在 i = 0 时已经完整展开了，第 1 位再放一次 a 只会产生一模一样的子树；
• i = 2 选 b：字符不同，正常进入。

关键在于第三个条件 !hasUsed[i - 1] 的取反语义：如果 hasUsed[i-1] 为 true，说明前一个相同字符正在当前路径上（是上层选入的），此时 chars[i] 作为"路径上第二个相同字符"是合法且必要的——例如 "aab" 的第二层就必须再选一个 a 才能得到 aab、baa。这正是"同位置剪重、跨层允许重复"的精确刻画，也是该剪枝条件最容易写错的地方。

4. 递归与撤销：标准的回溯三步

hasUsed[i] = true;                 // 做选择
s.append(chars[i]);
backtracking(chars, hasUsed, s);   // 递归
s.deleteCharAt(s.length() - 1);     // 撤销选择
hasUsed[i] = false;

使用 StringBuilder 而非 String 拼接，是因为 String 在 Java 中不可变，每次 + 都会新建对象；StringBuilder 让"追加/回退"都是 O(1)。只有当 s.length() == chars.length 时，路径才是完整排列，用 s.toString() 固化一份（toString 拷贝，避免后续修改污染已收集结果）存入 ret。

用 "abc" 手动走一遍决策树

对输入 abc（排序后不变），回溯展开如下（缩进表示递归深度）：

选 a
├── 选 b → 选 c  → 收集 abc
│          撤销 c
│       撤销 b
├── 选 c → 选 b  → 收集 acb
│          撤销 b
│       撤销 c
   撤销 a
选 b
├── 选 a → 选 c  → 收集 bac
├── 选 c → 选 a  → 收集 bca
   撤销 b
选 c
├── 选 a → 选 b  → 收集 cab
├── 选 b → 选 a  → 收集 cba
   撤销 c

最终 ret = [abc, acb, bac, bca, cab, cba]，与题目要求的字典序一致；若输入换成 aab，第 1 层第二个 a 被剪枝后，输出恰好为 [aab, aba, baa] 三个不重复的排列。

替代方案：交换法（不依赖 hasUsed）

除"逐个挑选"模型外，还有一个等价的交换模型：固定"当前位置 x"，让 x 之后的每个字符依次交换到 x 位，递归处理 x + 1，完成后换回。它不需要 hasUsed 数组，也不用预先排序（排序仅服务于字典序要求时），去重改用 HashSet 记录"本层已经用过哪些字符值"：

private List<String> res = new ArrayList<>();

public List<String> permutation(String s) {
    char[] arr = s.toCharArray();
    dfs(arr, 0);
    return res;
}

private void dfs(char[] arr, int x) {
    if (x == arr.length - 1) {          // 最后一位已确定，收集结果
        res.add(new String(arr));
        return;
    }
    HashSet<Character> set = new HashSet<>();
    for (int i = x; i < arr.length; i++) {
        if (set.contains(arr[i]))
            continue;                    // 本层重复字符值剪枝
        set.add(arr[i]);
        swap(arr, x, i);                 // 把第 i 个字符换到第 x 位
        dfs(arr, x + 1);
        swap(arr, x, i);                 // 换回，恢复现场
    }
}

private void swap(char[] arr, int i, int j) {
    char t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

注意两个方案的去重语义差异：

维度	hasUsed 剪枝方案（原题解）	交换法
去重依据	相邻位置字符相同 且 前一位置未被占用（!hasUsed[i-1]）	本层已出现过的字符值（HashSet）
是否需要排序	需要（字典序输出 + 相邻判重的前提）	不必须；若要求字典序输出仍需先排序
额外状态	一个 boolean[n] 数组	每层一个 HashSet，递归结束时随栈帧释放
路径表示	显式的 StringBuilder，收集时 toString()	数组本身即当前路径，收集时 new String(arr)

从源码结构看，两种写法的时间量级一致，区别只在实现形态；原题解采用的 hasUsed 版本与矩阵中的路径、机器人的运动范围 等"网格回溯"题共享同一套"visited 数组 + 撤销"骨架，便于在 CS-Notes 的「搜索」专题内互相印证。

复杂度分析

设字符串长度为 n、且字符互不重复：

• 时间复杂度 O(n · n!)：决策树有 n! 个叶子（每个叶子对应一个排列），收集每个结果需 O(n) 拷贝成字符串，加上内部节点上的循环开销，总量级为 n · n!。若含重复字符，剪枝会实际减少叶子数，但最坏界不变。
• 空间复杂度 O(n)：递归深度至多 n 层，每层持有循环变量与 hasUsed、StringBuilder 各 O(n)，即辅助空间 O(n)（不计输出数组 ret 本身占用的 O(n · n!)）。

工程上需要留意：n 稍大（如 n ≥ 10）时结果数量已达 360 万级，递归深度、结果内存与输出开销都会迅速放大，面试场景下建议主动说明该指数爆炸特性。

边界情况与实现细节

• 空字符串：原解法在入口即返回空列表，不会把 "" 本身当成一个排列输出；
• 单字符："a" 排序后进入递归，第 1 层选满即收集，输出 ["a"]；
• 全相同字符：如 "aaa"，第 1 层仅 i = 0 的分支存活，其余被剪掉，输出唯一结果 ["aaa"]，验证了去重剪枝的完备性；
• ret 作为成员变量：原解法用实例字段存放结果，方便在递归中直接追加；若在意线程安全或多次调用互不干扰，可把 ret 下沉为 Permutation 内的局部变量并作为参数传入（交换法中 res 同理）。

小结

本题是回溯模板的一次标准演练：先把问题建模成"n 层、每层做选点决策"的搜索树，再针对两个痛点各加一道剪枝——hasUsed 保证字符不重复使用，排序加 !hasUsed[i-1] 条件保证同层重复字符只展开一次。掌握这一模式后，可直接迁移到所有"给定元素集合、构造不重复序列"的问题上；而 CS-Notes 仓库中剑指 Offer 39～68 的其余题目以及 LeetCode 46/47（全排列 / 含重复元素的全排列）正是同一思想的延续训练。