842. 排列数字
摘要
Title: 842. 排列数字
Tag: DFS
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
842. 排列数字
-
题意
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。 -
思路
DFS爆搜+回溯
每次遍历这n个数，看哪个数空闲，若空闲就接着DFS，并标记状态 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26'''
Author: NEFU AB-IN
Date: 2022-03-01 23:17:33
FilePath: \ACM\Acwing\842.py
LastEditTime: 2022-03-01 23:26:06
'''
N = 10
path, st = [0] * N, [0] * N
def dfs(x):
if x == n + 1:
for i in range(1, n + 1):
print(path[i], end=" ")
print()
return
for i in range(1, n + 1): # 看i这个数字能不能放在x这个地方
if not st[i]:
path[x] = i
st[i] = 1
dfs(x + 1)
st[i] = 0
n = int(input())
dfs(1)