Lesson 28: 全排列 — 回溯法入门

练习任务

难度：中

给定一个字符串，输出其中所有字符的全排列，每行一个。

实现 permute(str, l, r) 函数，其中 swap 辅助函数已提供。这是**回溯算法（Backtracking）**的经典入门题，也是后续八皇后问题（Lesson 29）和 DFS 迷宫（Lesson 43）的基础。

本课共有 3 组测试用例：

输入 "ABC" → 输出 6 行: ABC, ACB, BAC, BCA, CBA, CAB
输入 "AB"  → 输出 2 行: AB, BA
输入 "A"   → 输出 1 行: A

提示：回溯的核心是三步曲——选择（swap 把候选换到固定位置）、递归（深入下一个位置）、撤销（swap 恢复原状）。想一想：为什么需要"撤销"？如果不撤销，会出现什么结果？这正是理解回溯的关键试金石。

核心知识点

回溯三要素 — 选择（枚举候选）、约束（全排列无额外约束）、目标（l==r 输出）
swap-递归-swap 三步曲 — 选择 → 递归 → 撤销，是回溯算法的标准模板
排列树结构 — 树的高度 = n，每层分支递减（n → n-1 → ... → 1），叶子数 = n!
撤销 swap 是正确性基石 — 忘撤销导致字符串被永久打乱，后续分支在脏数据上操作
去重剪枝 — i > l && str[i] == str[l] 跳过重复分支，避免输出重复排列
原地 swap vs 拷贝数组 — swap 空间 O(1)，拷贝 O(n)；前者更优
时间复杂度 O(n×n!) — 每个排列需 O(n) 打印，共 n! 个解，是问题固有的下界
递归调用栈追踪 — 最大深度 n，每层帧记录 l 和当前 i 的值

代码框架

28_permutations.c

#include <stdio.h>
#include <string.h>

/* 交换两个字符 */
void swap(char *a, char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

/* 全排列函数：输出字符串的所有排列 */
void permute(char *str, int l, int r)
{
    // 如果 l == r，说明所有位置都已确定
    // 在这里打印当前字符串（一个完整排列）

    // 枚举 i 从 l 到 r 的所有字符作为 l 位置的候选
    // 在这里实现循环：for (int i = l; i <= r; i++) { ... }

    // 把候选换到固定位置：swap(&str[l], &str[i])

    // 递归处理 l+1 之后的子问题：permute(str, l + 1, r)

    // 回溯：把候选换回来（恢复原状态，继续尝试下一个候选）
}

int main(void)
{
    char str[256];

    // 在这里读取输入并去掉换行符
    // fgets(str, sizeof(str), stdin);
    // int len = strlen(str);
    // if (len > 0 && str[len - 1] == '\n') str[len - 1] = '\0';

    // 在这里调用 permute(str, 0, strlen(str) - 1);

    return 0;
}

阅读骨架后，尝试自己填充 // 在这里... 标记的部分。核心挑战在于：回溯三步曲的每一步分别做什么？为什么不撤销会导致结果错乱？循环的边界是 i <= r 吗？

TIP

先不要往下翻看参考解答。尝试在白纸上用 "ABC" 手动追踪swap + 递归 + swap 的三步曲——第一轮 i=0 swap 不变，继续递归；第二轮 i=1 把 B 换到位置 0，探索后恢复。这能帮你建立回溯的直觉。

深度讲解

1. 回溯三步曲：swap → 递归 → 撤销 swap

1.1 什么是回溯

回溯（Backtracking）是一种系统搜索问题解的算法范式。核心思想是：逐步构建解，每走一步都评估当前部分解是否可能通向完整解；如果当前路径不可能成功，就退回（回溯）上一步，尝试其他选择。

回溯与暴力枚举的本质区别在于状态恢复——在尝试一个分支后，必须恢复现场，才能正确尝试下一个分支。

1.2 三步曲分解

全排列的回溯模板精炼为三步：

┌──────────────────────────────────────────────────────┐
│                    回溯三步曲                          │
├──────────┬───────────────────────┬────────────────────┤
│ 步骤     │ 代码                  │ 含义               │
├──────────┼───────────────────────┼────────────────────┤
│ 1. 选择  │ swap(&str[l],&str[i]) │ 将候选换到固定位置  │
│ 2. 递归  │ permute(str,l+1,r)    │ 解决更小的子问题    │
│ 3. 撤销  │ swap(&str[l],&str[i]) │ 恢复原状，尝试下一个 │
└──────────┴───────────────────────┴────────────────────┘

backtrack_template.c

void permute(char *str, int l, int r)
{
    if (l == r) {                    // 目标：所有位置已确定
        printf("%s\n", str);
        return;
    }

    for (int i = l; i <= r; i++) {
        // 第 1 步：做选择 — 把 str[i] 换到位置 l
        swap(&str[l], &str[i]);

        // 第 2 步：递归 — 解决 l+1 到 r 的子问题
        permute(str, l + 1, r);

        // 第 3 步：撤销选择 — 恢复原状
        swap(&str[l], &str[i]);
    }
}

1.3 逐行跟踪：以 "ABC" 为例

字符串初始: "ABC", l=0, r=2

═══════════════════════════════════════════════════════
第一轮: l=0, i=0 — 把 A 放到位置 0（A 本来就在位置 0）
═══════════════════════════════════════════════════════

  swap(&str[0], &str[0])     →  字符串: "ABC"  (A↔A，无变化)
  permute("ABC", 1, 2)       →  递归进入 l=1
    ┌─ l=1, i=1: swap(&str[1],&str[1]) → "ABC" (B↔B)
    │  permute("ABC", 2, 2) → l==2==r → 输出 "ABC" ✓ (第1个解)
    │  swap(&str[1],&str[1]) → "ABC" (恢复)
    │
    ├─ l=1, i=2: swap(&str[1],&str[2]) → "ACB" (B↔C)
    │  permute("ACB", 2, 2) → l==2==r → 输出 "ACB" ✓ (第2个解)
    │  swap(&str[1],&str[2]) → "ABC" (恢复，回溯！)
    │
    └─ l=1 循环结束，返回 l=0
  swap(&str[0], &str[0])     →  字符串: "ABC" (恢复)

═══════════════════════════════════════════════════════
第二轮: l=0, i=1 — 把 B 换到位置 0
═══════════════════════════════════════════════════════

  swap(&str[0], &str[1])     →  字符串: "BAC"  (A↔B)
  permute("BAC", 1, 2)       →  递归进入 l=1
    ┌─ l=1, i=1: swap(&str[1],&str[1]) → "BAC" (A↔A)
    │  permute("BAC", 2, 2) → 输出 "BAC" ✓ (第3个解)
    │  swap(&str[1],&str[1]) → "BAC" (恢复)
    │
    ├─ l=1, i=2: swap(&str[1],&str[2]) → "BCA" (A↔C)
    │  permute("BCA", 2, 2) → 输出 "BCA" ✓ (第4个解)
    │  swap(&str[1],&str[2]) → "BAC" (恢复)
    │
    └─ l=1 循环结束，返回 l=0
  swap(&str[0], &str[1])     →  字符串: "ABC" (恢复，回溯！)

═══════════════════════════════════════════════════════
第三轮: l=0, i=2 — 把 C 换到位置 0
═══════════════════════════════════════════════════════

  swap(&str[0], &str[2])     →  字符串: "CBA"  (A↔C)
  permute("CBA", 1, 2)       →  递归进入 l=1
    ┌─ l=1, i=1: swap(&str[1],&str[1]) → "CBA" (B↔B)
    │  permute("CBA", 2, 2) → 输出 "CBA" ✓ (第5个解)
    │  swap(&str[1],&str[1]) → "CBA" (恢复)
    │
    ├─ l=1, i=2: swap(&str[1],&str[2]) → "CAB" (B↔A)
    │  permute("CAB", 2, 2) → 输出 "CAB" ✓ (第6个解)
    │  swap(&str[1],&str[2]) → "CBA" (恢复)
    │
    └─ l=1 循环结束，返回 l=0
  swap(&str[0], &str[2])     →  字符串: "ABC" (恢复)

最终输出顺序: ABC → ACB → BAC → BCA → CBA → CAB

2. 排列树：树高 n，叶 n!

2.1 排列树的完整结构

以 ABC 为例，整个搜索过程形成一棵排列树：

                        位置 0                      位置 1           位置 2 (叶子)
                        ┌───┐
                        │ABC│  l=0, 所有位置待定
                        └─┬─┘
            ┌─────────────┼─────────────┐
        i=0:A↔A        i=1:A↔B        i=2:A↔C
        ┌───┐           ┌───┐           ┌───┐
        │ABC│           │BAC│           │CBA│  l=0 已定
        └─┬─┘           └─┬─┘           └─┬─┘
      ┌───┴───┐         ───┴───┐       ┌────┴───┐
   i=1:B↔B  i=2:B↔C i=1:A↔A  i=2:A↔C i=1:B↔B  i=2:B↔A
   ┌───     ┌───┐   ┌───┐   ┌───┐   ┌───┐   ┌───┐
   │ABC│   │ACB│   │BAC│   │BCA│   │CBA│   │CAB│  l=1 已定
   └─┬─┘   └─┬─┘   └─┬─┘   └─┬─┘   └─┬─┘   └─┬─┘
  i=2:C↔C  i=2:B↔B  i=2:C↔C  i=2:A↔A  i=2:A↔A  i=2:B↔B
   ┌───┐   ┌───┐   ┌───     ┌───     ┌───┐   ┌───┐
   │ABC│   │ACB│   │BAC│   │BCA│   │CBA│   │CAB│  l==r, 输出!
   └───┘   └───┘   └───     └───┘   └───┘   └───┘
     1       2       3       4       5       6

关键观察：

树的高度 = 字符串长度（每个位置一层）
叶子节点 = 完整排列，叶子数 = n!（这是排列次总数的阶乘公式）
每个内部节点的分支数 = r - l + 1，即剩余未固定的字符数
第 0 层 n 个分支，第 1 层 n-1 个，...，第 n-1 层 1 个
DFS 遍历顺序列树沿最左分支走到底，然后回溯

2.2 内部节点数分析

层级	节点数	每个节点分支数	总分支数
0	1	n	n
1	n	n-1	n(n-1)
2	n(n-1)	n-2	n(n-1)(n-2)
...	...	...	...
n-1 (叶)	n!	0	0

总内部节点数 ≈ n! × (1/1! + 1/2! + ... + 1/(n-1)!) ≈ (e - 1) × n! ≈ 1.718 × n!

3. 撤销 swap 是正确性基石：忘撤销的级联污染

3.1 如果不撤销会怎样？

这是理解回溯的最关键问题。让我们用 "ABC" 手动追踪如果忘记写第二个 swap 会怎样：

字符串: "ABC", l=0, r=2

i=0: swap(0,0) → "ABC" → permute(l=1) → swap(0,0) → "ABC" (恢复了)
i=1: swap(0,1) → "BAC" → permute(l=1) → 【忘了 swap(0,1) 恢复！】
     此时字符串仍然是 "BAC"！！！
i=2: swap(0,2) → "CAB"  ← ⚠ 本来应该把 str[2]='C' 换到位置 0，
           但因为字符串被上次破坏成了 "BAC"：
           str[0]='B', str[2]='C'，swap(0,2) 后变成 "CAB"
           这说明 for 循环并没有在正确的字符串上操作！

级联污染的完整链条：

┌────────────────────────────────────────────────────────┐
│ 正确流程 (有撤销):                                       │
│                                                        │
│ i=0: swap(0,0)="ABC" → 递归... → swap(0,0)="ABC" ✓    │
│       ↓ 字符串已恢复                                    │
│ i=1: swap(0,1)="BAC" → 递归... → swap(0,1)="ABC" ✓    │
│       ↓ 字符串已恢复                                    │
│ i=2: swap(0,2)="CBA" → 递归... → swap(0,2)="ABC" ✓    │
│                                                        │
├────────────────────────────────────────────────────────┤
│ 错误流程 (忘撤销):                                       │
│                                                        │
│ i=0: swap(0,0)="ABC" → 递归... → swap(0,0)="ABC" ✓    │
│       ↓ 字符串已恢复                                    │
│ i=1: swap(0,1)="BAC" → 递归... → ✗ 没恢复！             │
│       ↓ 字符串仍是 "BAC" ← 已被污染！                    │
│ i=2: swap(0,2)="CAB" ← 在脏数据上操作，完全错了！         │
│                                                        │
│ 递归过程中以为自己在处理 "CBA" 开头的分支，              │
│ 实际上字符串已经被打乱，产生完全错误的输出。              │
└─────────────────────────────────────────────────────────┘

WARNING

撤销操作不是可选的，它是回溯算法的定义性操作。没有撤销，就不是回溯，而是"乱改一通"。在任何回溯问题（全排列、八皇后、数独、迷宫）中，递归返回后必须恢复现场。

4. 去重剪枝：处理重复字符

4.1 问题：有重复字符时会发生什么

当前算法假设输入字符串没有重复字符。如果有重复（如 "AAB"），会输出重复的排列：

输入 "AAB"：
  AAB  AAB  ABA  ABA  BAA  BAA  (6 行，但有重复!)

实际上只有 3 种不同的排列: AAB  ABA  BAA
重复原因: 两个 'A' 被当成不同的字符在处理

4.2 解决方案：swap 前检查

在 swap 之前增加去重检查——如果 str[i] 和当前位置 l 的字符相同、且 i > l，就跳过：

dedup_pruning.c

void permute(char *str, int l, int r)
{
    if (l == r) {
        printf("%s\n", str);
        return;
    }

    for (int i = l; i <= r; i++) {
        // 去重剪枝：如果 str[i] 与 str[l] 相同且不是同一位置，跳过
        if (i > l && str[i] == str[l])
            continue;

        swap(&str[l], &str[i]);
        permute(str, l + 1, r);
        swap(&str[l], &str[i]);
    }
}

4.3 为什么只在 i > l 时检查？

以 "AAB" 为例，l=0 时：
  i=0: 第一个 'A' → 不跳过（i == l，需要处理）
  i=1: 第二个 'A' → 跳过（i > l && str[1] == str[0]）
  i=2: 'B'        → 不跳过（str[2] != str[0]）

以 "ABA" 为例，当 swap 改变了字符串内容后：
  在子问题内部，"AAB" 的 l=1 处只有 "AB" 两个字符
  i=1: 'A' 不跳过
  i=2: 'B' 不跳过（str[2] != str[1]）

NOTE

这个剪枝条件的前提是字符串已被排序（相同字符相邻），或者每次比较 str[i] == str[l] 能捕捉到相同字符。对于一般情况，更通用的去重方法是用一个 bool used[256] 数组标记当前递归层已经处理过的字符。

5. 为何用 swap 而不是拷贝数组

5.1 两种方案针比比

swap_vs_copy.c

// 方案 A: swap 原地操作（推荐）
void permute_swap(char *str, int l, int r)
{
    if (l == r) { printf("%s\n", str); return; }
    for (int i = l; i <= r; i++) {
        swap(&str[l], &str[i]);        // O(1) 操作
        permute_swap(str, l + 1, r);
        swap(&str[l], &str[i]);        // O(1) 操作
    }
}

// 方案 B: 拷贝数组（不推荐）
void permute_copy(char *str, int l, int r)
{
    if (l == r) { printf("%s\n", str); return; }
    for (int i = l; i <= r; i++) {
        char *copy = malloc(r - l + 2); // O(n) 分配！
        strcpy(copy, str);              // O(n) 拷贝！
        swap(&copy[l], &copy[i]);
        permute_copy(copy, l + 1, r);
        free(copy);                     // O(1) 释放
    }
}

维度	swap 方案	拷贝数组方案
每次递归的额外时间	O(1)（一次交换）	O(n)（malloc + strcpy + free）
每次递归的额外空间	O(1)（无分配）	O(n)（新数组）
总时间复杂度	O(n! × 1) = O(n!)	O(n! × n)（更差）
撤销方式	swap 恢复	free 释放整个数组

结论：swap 方案在时间和空间上都远优于拷贝方案。swap 利用了"只需要修改两个位置"的特性，实现了 O(1) 的选择和撤销。

6. 时间复杂度 O(n×n!)：问题固有下界

6.1 复杂度分析

指标	值	说明
叶子节点数	n!	每个叶子代表一个完整排列
内部节点数	≈ (e-1) × n! ≈ 1.718 × n!	等比级数求和
每个叶子的输出时间	O(n)	打印 n 个字符 + '\n'
每个内部节点的工作	O(1)	一次 swap + 一次递归调用
总时间复杂度	O(n × n!)	n! 个输出 × 每个 O(n)

6.2 为什么这是问题固有的

全排列的输出规模本身就是 n! 个排列，每个排列包含 n 个字符。任何一个算法都必须至少输出所有 n! × n 个字符——这意味着 O(n × n!) 是问题的信息论下界。算法已经以 O(1) 的额外代价（swap）生成每个排列，是最优的。

指数爆炸的直观感受：

  n   | n!          | 输出行数 | 大约耗时
  ─────┼─────────────┼─────────┼─────────
  3    | 6           | 6        | < 1ms
  5    | 120         | 120      | < 1ms
  8    | 40,320      | 40,320   | ~50ms
  10   | 3,628,800   | 360 万行  | ~3s
  12   | 479,001,600 | 4.8 亿行  | 不可承受

7. 递归调用栈跟踪

7.1 调用栈的可视化

以 "ABC" 为例，递归调用栈的演变过程：

main() 调用 permute("ABC", 0, 2)
│
├─ permute(l=0): i=0, swap(0,0)="ABC"
│  ├─ permute(l=1): i=1, swap(1,1)="ABC"
│  │  └─ permute(l=2): l==r → printf("ABC") → 返回
│  │  swap(1,1)="ABC"
│  ├─ permute(l=1): i=2, swap(1,2)="ACB"
│  │  └─ permute(l=2): l==r → printf("ACB") → 返回
│  │  swap(1,2)="ABC"
│  └─ 返回
│  swap(0,0)="ABC"
│
├─ permute(l=0): i=1, swap(0,1)="BAC"
│  ├─ permute(l=1): i=1, swap(1,1)="BAC"
│  │  └─ permute(l=2): l==r → printf("BAC") → 返回
│  │  swap(1,1)="BAC"
│  ├─ permute(l=1): i=2, swap(1,2)="BCA"
│  │  └─ permute(l=2): l==r → printf("BCA") → 返回
│  │  swap(1,2)="BAC"
│  └─ 返回
│  swap(0,1)="ABC"
│
└─ permute(l=0): i=2, swap(0,2)="CBA"
   ... (类似过程，输出 CBA 和 CAB)
   swap(0,2)="ABC"

最大递归深度: 3 层（l=0 → l=1 → l=2）。对于长度为 n 的字符串，最大递归深度 = n。

7.2 栈帧的内容

每次递归调用压入的栈帧包含：
┌──────────────────────┐
│ 返回地址              │ ← 递归调用后的下一条指令地址
│ str 指针              │ ← 指向字符串首地址
│ l 的值                │ ← 当前固定位置
│ r 的值                │ ← 字符串末尾索引（不变）
│ i 的当前值（循环变量）  │ ← 当前正在尝试的候选索引
└──────────────────────┘

NOTE

回溯的优雅之处在于：递归调用的栈帧自动保存了循环变量 i 的状态。当递归返回时，循环恰好从 i+1 继续——这就是"自动管理状态"的强大之处。

参考解答

练习: permute 完整实现

solution_28_permutations.c

#include <stdio.h>
#include <string.h>

/* 交换两个字符 */
void swap(char *a, char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}

/* 全排列函数：输出字符串的所有排列 */
void permute(char *str, int l, int r)
{
    if (l == r) {
        printf("%s\n", str);          /* 到达叶子，输出一个完整排列 */
        return;
    }

    for (int i = l; i <= r; i++) {
        swap(&str[l], &str[i]);       /* 1. 选择：把 str[i] 换到位置 l */
        permute(str, l + 1, r);       /* 2. 递归：处理后面的位置 */
        swap(&str[l], &str[i]);       /* 3. 撤销：恢复原状 */
    }
}

int main(void)
{
    char str[256];

    fgets(str, sizeof(str), stdin);

    /* 去掉末尾换行符 */
    int len = strlen(str);
    if (len > 0 && str[len - 1] == '\n')
        str[len - 1] = '\0';

    permute(str, 0, strlen(str) - 1);

    return 0;
}

核心逻辑解析：

终止条件 l == r：所有位置都已确定，当前字符串就是一个完整排列，打印即可。
三步曲：swap（选择候选字符放到位置 l）→ permute（递归深入）→ swap（恢复，准备尝试下一个候选）。
循环边界 i <= r：从 l 到 r 的所有字符都可以作为位置 l 的候选。
为什么是 i = l 开始：i == l 意味着"不动"，即当前的 str[l] 自己作为候选。

对照检查：递归终止条件是 l == r 吗？循环从 i = l 开始了吗？两次 swap 对称写了吗？printf 在递归终止分支里吗？

课堂讨论

如果去掉第二个 swap（即忘记撤销），对 "ABC" 调用 permute(str, 0, 2) 会输出什么结果？为什么？
回溯算法中的"三步曲"和日常见的活中的"尝试-评估-撤回"有什么对应关系？你能举一个非编程的例子吗？
循环变量 i 从 l 开始而不是从 0 开始——为什么？如果改成 i = 0 会怎样？
全排列问题能否用迭代（非递归）方式解决？如果可以，和递归方案相比有什么优缺点？
如果输入字符串非常长（如 100 个字符），这个算法的可行性如何？有什么现实场景需要处理这么大规模的全排列？

讨论答案

Q1: 去掉第二个 swap 会输出什么吗？

如果忘记撤销，字符串会被永久打乱。以 "ABC" 为例：

i=0：正常，swap(0,0) 不改变字符串，递归输出 ABC 和 ACB，swap(0,0) 恢复
i=1：swap(0,1) 得到 "BAC"，递归...，忘撤销，字符串留在 "BAC"
i=2：现在要 swap(0,2)，但字符串已经是 "BAC"！swap(0,2) 变成 "CAB"——此时 str[0]='B', str[2]='C'。接下来的输出完全错误。

原因：下一轮循环在已被破坏的字符串上操作，产生了"级联污染"。这正是回溯算法必须撤销选择的根本原因——保证每次循环迭代都在同一个干净的起始状态上开始。

Q2: 回溯与日常生活的对应

回溯算法与生活中许多"试错"过程非常相似：

例子 1：解密码锁 3 位数字密码，从 000 开始试：001, 002, ... 到 999。如果发现某一位"不对"，就需要把后面的位数"复位"重新试——这就是回溯的"撤销"。

例子 2：走迷宫 走进一条死胡同，你需要退回到上一个分岔口，然后尝试另一个方向。在地板上划线标记你走过的路，退回来时擦掉——划线 = 选择，擦掉 = 撤销。

例子 3：拼图 尝试一一块拼图放在某个位置，发现不对就拿下来换另一块——"拿下来"就是回溯。

回溯的核心哲学是：大胆假设，小心验证，不行就退。这在 AI 搜索、博弈论（象棋 AI）中也是基础思想。

Q3: i 从 l 开始而不是从 0？

// ❌ 错误：i 从 0 开始
for (int i = 0; i <= r; i++) {
    swap(&str[l], &str[i]);    // 搅乱了已固定的位置！
    permute(str, l + 1, r);
    swap(&str[l], &str[i]);
}

// ✅ 正确：i 从 l 开始
for (int i = l; i <= r; i++) {
    swap(&str[l], &str[i]);    // 只修改 l 及之后的位置
    permute(str, l + 1, r);
    swap(&str[l], &str[i]);
}

如果 i 从 0 开始，会把已经固定好的位置再次打乱。例如 l=1 时，位置 0 已经确定了字符，但 i=0 的 swap 会把它换走——这破坏了"位置 0 到 l-1 是已确定前缀"的不变式。

i = l 的含义是：位置 l 的候选只能从尚未确定的位置（l 到 r）中选择，不能动已经固定的部分。

Q4: 全排列能否迭代解决？

可以，但代码更复杂。两种经典迭代方法：

方法 1：字典序算法（next_permutation）

// C++ 风格的 next_permutation
// 1. 从右向左找第一个递减位置
// 2. 从右向左找第一个大于该值的元素，交换
// 3. 反转后面的子数组

方法 2：手动栈模拟递归 用 struct Frame { int l, i; } 数组模拟递归栈，手动 push/pop。

对比：

维度	递归	迭代
代码简洁性	极简洁（6 行）	冗长
可读性	高度直观	需要理解栈逻辑
栈溢出风险	n 太大时可以溢出	可用堆内存
避免
调试难度	较易（调用栈清晰）	较难（需手动追踪）

对于教学和学习，递归方案远优于迭代方案——因为它直接对应回溯的思想模型。迭代方案更适合对栈溢出敏感的生产环境。

Q5: 超长字符串全排列的可行性

不可行。n! 增长极其迅猛：

n=20 时，20! ≈ 2.43 × 10^18，即 243 亿亿个排列
即使每秒处理 10 亿个排列，也需要约 77 年才能完成

现实场景：

密码破解：只关心"找到正确密码"，不关心生成所有排列
旅行商问``（TSP）：n 个城市的所有访问顺序是 n!，但可以移动动态规划或分支定界！枝
大规模排列问题通常不要求全部列出，而是用启发式搜索、随机采样或遗传算法

课后练习

实现去重全排列。修改permute 函数，使其能正确处理包含重复字符的字符串。"AAB" 应输出不重复的 3 行。

知识点提示：在 swap 前检查是否有相同字符已被处理过。方法一：用 bool used[256] = {false} 数组标记本层已枚举的字符。方法二：排序后检查 i > l && str[i] == str[i-1]。

参考解答

dedup_permutations.c

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

void swap(char *a, char *b) {
    char tmp = *a; *a = *b; *b = tmp;
}

void permute(char *str, int l, int r)
{
    if (l == r) {
        printf("%s\n", str);
        return;
    }

    bool used[256] = {false};  /* 标记本层已枚举的字符 */

    for (int i = l; i <= r; i++) {
        /* 如果这个字符在本层已经被 swap 到过位置 l，跳过*/
        if (used[(unsigned char)str[i]])
            continue;
        used[(unsigned char)str[i]] = true;

        swap(&str[l], &str[i]);
        permute(str, l + 1, r);
        swap(&str[l], &str[i]);
    }
}

int main(void)
{
    char str[256];
    fgets(str, sizeof(str), stdin);
    int len = strlen(str);
    if (len > 0 && str[len - 1] == '\n') str[len - 1] = '\0';

    permute(str, 0, strlen(str) - 1);
    return 0;
}

要点：used 数组在递归的每一层独立创建（因为是局部变量），记录了当前层已处理过的字符。注意 unsigned char 的转换——避免 char 有符号时的数组越界。

字典序全排列。修改 permute 的实现，使输出按字典序排列。提示：在 permute 开始前先对字符串排序（qsort），然调用用 next_permutation 的迭代方式，或者改变回溯的遍历顺序。

知识点提示：C 标准库的 qsort 函数可以对字符数组排序。按字典序输出排列的一个简单做法是：在调用 permute 之前先对字符串排序，然后确保递归过程中相对顺序不变（即只在 [l, r] 范围内操作）。

参考解答

lexicographic_permute.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void swap(char *a, char *b) {
    char tmp = *a; *a = *b; *b = tmp;
}

int cmp_char(const void *a, const void *b) {
    return *(const char *)a - *(const char *)b;
}

void permute(char *str, int l, int r)
{
    if (l == r) {
        printf("%s\n", str);
        return;
    }

    /* 对 l..r 部分排序，保证同层按字典序遍历候选 */
    qsort(str + l, r - l + 1, sizeof(char), cmp_char);

    for (int i = l; i <= r; i++) {
        swap(&str[l], &str[i]);
        permute(str, l + 1, r);
        swap(&str[l], &str[i]);
    }
}

int main(void)
{
    char str[256];
    fgets(str, sizeof(str), stdin);
    int len = strlen(str);
    if (len > 0 && str[len - 1] == '\n') str[len - 1] = '\0';

    qsort(str, strlen(str), sizeof(char), cmp_char);
    permute(str, 0, strlen(str) - 1);
    return 0;
}

注意：每层递归对 [l, r] 范围内调用 qsort 会永久改变该区间内字符的相对顺序，swap 的成对操作只保证位置 l 的字符被恢复，后缀 [l+1, r] 的实际顺序是 qsort 重排后的结果。不过这只影响递归层内的遍历顺序，不影响最终输出的完整性和字典序排列。

只生成前 k 个排列。修改 permute，增加一个全局计数器，只打印前 k 个排列后立即退出所有递归。传入 k=3，对 "ABCD" 应该只输出 3 行。

知识点提示：全局变量 int k 和 int count。在叶子节点处 count++；当 count >= k 时，所有递归层立即返回（可以用 return 或检查 count < k 作为进入下一层的前提）。

参考解答

first_k_permutations.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int k, count;  /* k = 需要输出的排列数, count = 已输出计数 */

void swap(char *a, char *b) {
    char tmp = *a; *a = *b; *b = tmp;
}

void permute(char *str, int l, int r)
{
    if (l == r) {
        if (count < k) {
            printf("%s\n", str);
            count++;
        }
        return;
    }

    for (int i = l; i <= r; i++) {
        if (count >= k) return;  /* 已输出足够，提前终止 */

        swap(&str[l], &str[i]);
        permute(str, l + 1, r);
        swap(&str[l], &str[i]);
    }
}

int main(void)
{
    char str[256];

    /* 第一行：读入字符串 */
    fgets(str, sizeof(str), stdin);
    int len = strlen(str);
    if (len > 0 && str[len - 1] == '\n') str[len - 1] = '\0';

    /* 第二行：读入 k */
    char k_buf[32];
    fgets(k_buf, sizeof(k_buf), stdin);
    k = atoi(k_buf);

    count = 0;
    permute(str, 0, strlen(str) - 1);
    return 0;
}

关键：在叶子节点和 for 循环内部都检查 count >= k，确保一旦满足条件就立即从所有递归层返回，避免不必要的计算。

回溯框架迁移：生成所有子集。给定字符串 str，用回溯算法生成其所有子集（每个字符可选可不选）。例如 "AB" 的子集为 ""、"A"、"B"、"AB"，每行一个

知识点提示：这不再是全排列（关注顺序），而是子集问题（关注选与不选）。回溯思路：对每个位置 i，有两种选择——选 str[i] 进入子集，或不选。递归树是二叉树（每个位置选/不选），深度 n，叶子数 2^n。

参考解答

all_subsets.c

#include <stdio.h>
#include <string.h>

/* subset[] 存储当前构建的子集，subset_size 是当前大小 */
void gen_subsets(char *str, int idx, int n,
                 char *subset, int subset_size)
{
    if (idx == n) {
        /* 到达叶子：输出当前子集 */
        for (int i = 0; i < subset_size; i++)
            putchar(subset[i]);
        putchar('\n');
        return;
    }

    /* 分支 1: 不选 str[idx] */
    gen_subsets(str, idx + 1, n, subset, subset_size);

    /* 分支 2: 选 str[idx] */
    subset[subset_size] = str[idx];
    gen_subsets(str, idx + 1, n, subset, subset_size + 1);
    /* 无需显式撤销，因为 subset_size 是值传递 */
}

int main(void)
{
    char str[256], subset[256];
    fgets(str, sizeof(str), stdin);
    int len = strlen(str);
    if (len > 0 && str[len - 1] == '\n') str[len - 1] = '\0';

    gen_subsets(str, 0, strlen(str), subset, 0);
    return 0;
}

观察：子集问题中，"撤销"不是通过 swap，而是通过值传递 subset_size——递归函数的参数不修改调用者的变量，返回时自然恢复。这是回溯的另一种形式。

参考资料

《算法导论》(CLRS) 第 4 版 — 回溯算法章节，覆盖排列、组合、子集等经典问题
Sedgewick《算法》第 4 版 §2.3 — 递归与回``，含排列生成的详细分析
《数据结构与算法分析 — C 语言描述》§10.5 — 回溯算法，从八皇后到一般回溯框架
GeeksforGeeks: Permutations of a String — swap-based backtracking 的逐步图文讲解

"The best way to understand backtracking is to trace through a small example by hand. You'll see the pattern: dive in, hit bottom, back up one step, try the next branch." — 回溯学习者的普遍心得

Lesson 28: 全排列 — 回溯法入门 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. 回溯三步曲：swap → 递归 → 撤销 swap ​

1.1 什么是回溯 ​

1.2 三步曲分解 ​

1.3 逐行跟踪：以 "ABC" 为例 ​

2. 排列树：树高 n，叶 n! ​

2.1 排列树的完整结构 ​

2.2 内部节点数分析 ​

3. 撤销 swap 是正确性基石：忘撤销的级联污染 ​

3.1 如果不撤销会怎样？ ​

4. 去重剪枝：处理重复字符 ​

4.1 问题：有重复字符时会发生什么 ​

4.2 解决方案：swap 前检查 ​

4.3 为什么只在 i > l 时检查？ ​

5. 为何用 swap 而不是拷贝数组 ​

5.1 两种方案针比比 ​

6. 时间复杂度 O(n×n!)：问题固有下界 ​

6.1 复杂度分析 ​

6.2 为什么这是问题固有的 ​

7. 递归调用栈跟踪 ​

7.1 调用栈的可视化 ​

7.2 栈帧的内容 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

课后练习 ​

参考资料 ​

Lesson 28: 全排列 — 回溯法入门

练习任务

核心知识点

代码框架

深度讲解

1. 回溯三步曲：swap → 递归 → 撤销 swap

1.1 什么是回溯

1.2 三步曲分解

1.3 逐行跟踪：以 "ABC" 为例

2. 排列树：树高 n，叶 n!

2.1 排列树的完整结构

2.2 内部节点数分析

3. 撤销 swap 是正确性基石：忘撤销的级联污染

3.1 如果不撤销会怎样？

4. 去重剪枝：处理重复字符

4.1 问题：有重复字符时会发生什么

4.2 解决方案：swap 前检查

4.3 为什么只在 i > l 时检查？

5. 为何用 swap 而不是拷贝数组

5.1 两种方案针比比

6. 时间复杂度 O(n×n!)：问题固有下界

6.1 复杂度分析

6.2 为什么这是问题固有的

7. 递归调用栈跟踪

7.1 调用栈的可视化

7.2 栈帧的内容

参考解答

课堂讨论

讨论答案

课后练习

参考资料