当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ2365全排列问题
4199+

题目大意:输出自然数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位可以换其他数字,即不填当前选的那个了,标记该数字没填过(用过)。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

SSOJ2365全排列问题:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!