递归实现排列型枚举

问题描述

升序输出所有$n$的全排列$(0< n<10)$

样例输入

3

样例输出

xxxxxxxxxx
1 2 3 
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

解题思路

类似递归实现指数型枚举和递归实现组合型枚举，cal函数的退出条件是x>n。

我们用一个数组$order$记录所选排列的顺序(每个数选择的是什么)，用一个布尔数组$chosen$来表示某个数是否选择过。

每次在所有没选过的数中选择一个，递归在剩下的数中选择一个...，递归回来后恢复现场，取消选择这个数。