HJ150. 全排列
题目描述
给定整数 n，按字典序输出 1 到 n 的所有排列。
输入格式
一行一个整数 n。
输出格式
每行输出一个排列（n 个整数，空格分隔），按字典序升序。
示例
示例 1
输入：
3
输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
说明： 1 到 3 的所有 6 种排列，按字典序升序输出。
解题思路
第一步：理解问题本质
生成 1 到 n 的所有排列，共 n! 种，并按字典序排列。本质是经典的全排列问题。
第二步：暴力解法（嵌套交换）
使用迭代式交换（如 Heap 算法）或逐个推导排列。
问题：此类方法生成顺序不保证字典序，且需要额外排序，逻辑复杂。
第三步：优化解法（回溯 / DFS）
用回溯法逐步构建排列：path 保存当前已选数字，used 记录哪些数字已用。每次从 1 到 n 中选一个未使用的数字填入当前位置，递归到长度为 n 时记录一个排列。
关键：从小到大遍历候选数字，天然保证生成的排列是字典序。
def backtrack():
if len(path) == n:
res.append(' '.join(map(str, path)))
return
for x in range(1, n + 1): # 从小到大，保证字典序
if not used[x]:
used[x] = True
path.append(x)
backtrack()
path.pop()
used[x] = False
第四步：最优解法
回溯法本身就是全排列问题的最优思路，时间复杂度 O(n·n!)（生成 n! 个排列，每个 O(n)），空间 O(n)（回溯栈 + used 数组）。
完整代码实现
算法可视化 · 逐帧回放这道题的代码70 帧 · 录制输入
import sys
def solve() -> None:
n = int(sys.stdin.readline().strip())
res = []
path = []
used = [False] * (n + 1)
def backtrack():
if len(path) == n:
res.append(' '.join(map(str, path)))
return
for x in range(1, n + 1): # 从小到大，保证字典序
if not used[x]:
used[x] = True
path.append(x)
backtrack()
path.pop()
used[x] = False
backtrack()
print('\n'.join(res))
if __name__ == "__main__":
solve()
示例推演
以示例 1 为例，n=3。
回溯过程（每次从 1 开始选，保证字典序）：
- 选 1 → 选 2 → 选 3，得到
1 2 3 - 回溯：退 3，选 3 → 得到
1 3 2 - 回溯：退到 1，退 2，选 2 → 选 1 → 选 3，得到
2 1 3 - 选 2 → 选 3 → 选 1，得到
2 3 1 - 选 3 → 选 1 → 选 2，得到
3 1 2 - 选 3 → 选 2 → 选 1，得到
3 2 1
完整字典序序列：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 交换法+排序 | O(n!·log n!) | O(n) | 需额外排序 |
| 回溯法 | O(n·n!) | O(n) | 生成 n! 个排列，天然字典序 |
易错点总结
1. 忘记回溯恢复状态
递归返回后必须 path.pop() 并 used[x] = False，否则状态被污染，导致排列缺失或错误。
2. 遍历顺序不保证字典序
若从大到小遍历候选，生成的是逆字典序。必须从 1 到 n 递增遍历。
3. used 数组大小
used 下标从 1 到 n，数组长度应为 n+1，写成 n 会越界。
扩展思考
- 若输入有重复元素，需要先排序并在回溯中跳过相同元素（
if i > 0 and nums[i]==nums[i-1] and not used[i-1]: continue）去重。 - 排列数增长极快（n!），n 较大时必须考虑剪枝或改用 next_permutation 迭代生成。