你好，同学。我们已经学习了“子集”和“组合”，它们属于组合数学中的选择问题。今天我们要攻克的是搜索算法中的另一座大山——全排列 (Permutations)。

全排列与组合最大的区别在于：顺序是有意义的。在 NOI 竞赛中，全排列是理解状态空间搜索、剪枝优化以及置换群论的基础。

一、 题目描述 (NOI 风格)

题目名称：全排列 (Permutations) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个包含 $n$ 个互不相同整数的序列 $A$。请设计一个算法，按任意顺序输出该序列的所有可能全排列。 全排列是指将序列中的所有元素重新排列，使得每个元素在每个排列中出现且仅出现一次。

【输入格式】 输入共两行。 第一行包含一个整数 $n$，表示序列中元素的个数。 第二行包含 $n$ 个以空格隔开的整数，表示序列 $A$ 中的元素。

【输出格式】 输出若干行，每行表示一个全排列，元素之间用空格隔开。

【样例输入】

3
1 2 3

【样例输出】

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

【数据范围】 对于 $100\%$ 的数据：$1 \le n \le 8$，序列中的元素互不相同，且每个元素均在 int 范围内。 （注：在实际竞赛中，$n$ 可能会达到 10 或 11，因为 $10! = 3,628,800$，仍在 1.0s 处理范围内。）

二、 预备知识点

1. 回溯算法 (Backtracking)：核心在于“尝试”与“撤销”。
2. 标记数组 (Used Array)：使用一个布尔数组 used 记录哪些元素已经被放入当前排列，防止重复使用。
3. 阶乘复杂度 ($n!$)：全排列的总数是 $n! = n \times (n-1) \times \dots \times 1$。
4. STL 函数库：了解 std::next_permutation 的底层原理。

三、 启发式思路引导：草稿纸上的推理

排列问题就像是在填空位。假设有 $n$ 个位置，我们要把 $n$ 个不同的数填进去。

1. 决策过程（图形化思考）

以 {1, 2, 3} 为例，画出搜索树：

• 第 1 位：可以填 1 或 2 或 3。
  • 若填了 1，则剩余 {2, 3}。
    • 第 2 位：可以填 2（剩 3）或填 3（剩 2）。
      • 第 3 位：只能填剩下的那个数。
• 关键点：当你填第 $i$ 位时，你需要知道哪些数在第 $1 \dots i-1$ 位已经“名花有主”了。

2. 状态维护

在草稿纸上画出一个 used 数组的快照：

• used(i) = true 表示第 $i$ 个数已被占用。
• used(i) = false 表示第 $i$ 个数目前可用。
• 回溯的真谛：当你从递归深层返回上一层时，必须把 used(i) 重新设为 false，否则上一层的其他分支就没法使用这个数了。

四、 复杂度分析与建议

• 时间复杂度分析：

  • 全排列共有 $n!$ 个。
  • 每个排列需要 $O(n)$ 的时间遍历和输出。
  • 总复杂度：$O(n \cdot n!)$。
  • 优化建议：当 $n$ 较大时，输出往往成为性能瓶颈。在 NOI 中建议使用 printf 或 "\n" 代替 endl。

• 空间复杂度分析：

  • 递归深度为 $O(n)$。
  • used 数组和存放当前排列的 path 数组占用 $O(n)$ 空间。

五、 算法流程图 (C++14 风格伪代码)

我们使用最经典、最利于竞赛扩展的“标记数组法”：

graph TD
    Start(开始) --> Init(初始化 used 数组全为 false)
    Init --> CallDFS("DFS(当前深度 0)")

    subgraph DFS_Process [递归函数 DFS-depth]
    Check{depth == n ?}
    Check -- Yes --> Save(输出当前 path 并返回)
    Check -- No --> LoopInit("循环 i 从 0 到 n-1")
    
    LoopInit --> IsUsed{used(i) 是 true 吗?}
    IsUsed -- Yes --> NextI("i++ 继续循环")
    IsUsed -- No --> Action("标记 used(i)=true")
    
    Action --> Push("path.push_back(nums(i))")
    Push --> Recur("递归 DFS(depth + 1)")
    Recur --> Pop("回溯: path.pop_back")
    Pop --> Unmark("恢复: used(i)=false")
    Unmark --> NextI
    end

    Save --> End(结束)
    NextI --> LoopEnd{循环结束?}
    LoopEnd -- Yes --> Return((返回上一层))

六、 读题关键词总结

在 NOI 竞赛中识别全排列题型的关键词：

1. “排列” (Permutation)：强调顺序，必须考虑所有元素的先后位置。
2. “互不相同” (Distinct)：这意味着我们不需要处理“相同元素产生的重复排列”问题（如果元素有重复，则需要排序+相邻去重判断）。
3. “所有可能” (All possible)：典型的搜索信号，说明要遍历完整的状态空间。
4. “任意顺序”：如果题目没要求字典序，我们可以用最快的搜索方式。但注意：如果题目要求按字典序输出，务必在搜索前先对原序列进行 std::sort，这样 DFS 跑出来的结果自然就是字典序。

教练寄语： 全排列是搜索算法中“状态回溯”最纯粹的体现。理解了如何通过 used 数组控制元素的“进”与“出”，你就掌握了 NOI 搜索题目的半壁江山。加油，多在纸上画画那棵搜索树！