94. 递归实现排列型枚举
摘要
Title: 94. 递归实现排列型枚举
Tag: dfs
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
94. 递归实现排列型枚举
-
题意
把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
-
思路
st记录是否用过，path表示路径
-
代码
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
27'''
Author: NEFU AB-IN
Date: 2022-03-21 15:26:33
FilePath: \ACM\Acwing\94.py
LastEditTime: 2022-03-21 15:26:33
'''
def dfs(u):
if u > n:
for i in range(1, n + 1):
print(path[i], end=" ")
print()
return
for i in range(1, n + 1):
if st[i] == 0:
st[i] = 1
path[u] = i
dfs(u + 1)
st[i] = 0
n = int(input())
st = [0] * (n + 1)
path = [0] * (n + 1)
dfs(1)