学习目标与前置知识

• 明确本题的搜索状态、合法选择和终止条件，并完成可运行的 C++17 解答。
• 用边界输入解释下面列出的常见错误，确认撤销、去重或最短距离的正确性。
• 前置：本章相关知识，以及 C++ 函数、数组/容器和递归；BFS 题还需要队列。

题目描述

给定正整数 n，将 1 到 n 每个数恰好使用一次，输出所有不同的排列。排列按字典序从小到大输出：比较两个排列时，第一处不同的数字较小者在前。

本 Lab 保留原题的标准输入/输出合同。

输入格式

一行一个整数 n。

输出格式

每行一个排列，每个数字占 5 个字符宽度并右对齐，行末换行。本地按空白分隔的 token 比较；提交洛谷时仍应遵守场宽要求。

数据范围

1 <= n <= 9。

样例输入

3

样例输出

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

状态与边界

路径保存已经选出的前缀，used[x] 表示数字 x 是否在当前路径中。

每次递归返回后同时撤销路径和 used；输出 n=9 的完整答案需要约 16.7 MB，不能只打印排列数。

复杂度目标

时间 O(n * n!)，除输出外辅助空间 O(n)。参考实现流式输出，不存储所有排列。

编写与测试

修改 student/main.cpp 中的 solve，保留现有读写框架。调试信息写入标准错误，标准输出只保留答案。测试清单和分值以 tests/cases.json 为准，总分 100 分；输入均符合本页约定。

在仓库根目录执行：

pnpm lab:run -- labs/chapter-15/exercise/E-15-01-permutations
pnpm lab:score -- labs/chapter-15/exercise/E-15-01-permutations

进入本 Lab 目录后也可运行 make run。作者核验命令为：

pnpm lab:verify -- labs/chapter-15/exercise/E-15-01-permutations

完成清单

• 学生程序编译成功，严格评分为 100/100。
• 能说明每个状态变量和终止条件，并解释复杂度。
• 能用一个最小反例说明本题的关键边界或常见错误。
• 输出的顺序、数量和空结果处理符合本页约定。

思考与复盘

1. 哪些信息必须随搜索路径恢复，哪些信息可以在整次搜索中保留？
2. 删除本页提到的一条约束或剪枝，会得到错误答案，还是仅仅变慢？用一个输入说明。
3. 输入达到上限时，时间、递归深度和输出量分别由什么决定？

题目来源与课程化说明

来源：洛谷 P1706 全排列问题。本 Lab 独立编写参考实现和测试数据，并按课程环境重新表述题面；完整参考代码位于 solution/main.cpp，不复制第三方题解或隐藏测试。