题目大意：输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入

输出

样例输入

3

样例输出

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

解题思路

把每个排列看成n个格子，一个一个格子填数字，每次只填前面没填过（没用过）的数字，这样填完n个之后就可以输出序列了。

用递归来写，dfs(k)表示填n个格子中的第k个，一开始从第一个开始填，递归结束的条件是n个格子都填完了，当k大于n时，表示正在填第k+1个，前面n个都填完了，这是可以输出，不再递归；否则，往第k个格子填数字，枚举1到n各个数字，没填过的才可以填，用一个u数组记录该数字是否用过，就不需要枚举a[1]到a[k-1]中填过的数字了，可以填就记录第k个数字是什么（a[k]），并标记数字填过（用过），填下一个格子，填完后（回溯），第k位可以换其他数字，即不填当前选的那个了，标记该数字没填过（用过）。

程序实现