[842]: # 排序数字python版
题目描述
给定一个整数n,将数字1~n排成一排,将会有很多种排列方法。
现在,请你按照字典序将所有的排列方法输出。
输入格式
共一行,包含一个整数n。
输出格式
按字典序输出所有排列方案,每个方案占一行。
数据范围
1≤n≤7
样例
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
算法1 DFS O(n)
1、确定递归状态dfs(i,path)
2、确定递归出口if len(path) == n:
3、扩展可能搜索的活节点
4、装入活节点值,向下一层继续递归
def dfs(i,path):
if len(path) == n:
print(' '.join(path))
return
for j in range(0,n):
if visited[j] == False:
path.append(str(nums[j]))
visited[j] = True
dfs(j, path)
visited[j] = False #回溯
path.pop()
n = int(input())
nums = [i+1 for i in range(n)]
visited = [False]*n
res = []
dfs(0,[])