SSOJ2365全排列问题
4199+
作者:crxis 发布:2017-07-28 分类:深度优先搜索
题目大意:输出自然数1到n所有不重复的排列,即n的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
输入
n(1<=n<=9)
输出
由1~n组成的所有不重复的数字序列,每一行一个序列,每个数字前4个空格。
样例输入
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位可以换其他数字,即不填当前选的那个了,标记该数字没填过(用过)。