牛客华为HJ77火车进站

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
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
28
29
30
31
32
33
34
35
36
37
38
39
40
# 这道题目考了俩个 考点：
# 1、dfs回溯算法 写全排列 参考 leecode 46. 全排列
# 2、判断是否为合法栈输出 参考 leecode 946. 验证栈序列
# 我在这里直接用两个方法 封装起来了,把判断是否合法 嵌入回溯算法中，不然用两个方法前后相衔接的方式写，会超时。。
def dfs(values,nums):
    path,result,used = [],[],[False for _ in range(nums)]
    def dfs_inner(values):
        if len(path)==nums:
            if illegal(path.copy()):     # 把判断是否合法 嵌入回溯算法中，不然用两个方法前后相衔接的方式写，会超时。
                result.append(path.copy())
        for i in range(nums):
            if used[i]==True:
                continue 
            used[i] = True 
            path.append(values[i])
            dfs_inner(values)       # 排列和组合这里有区别，这里是排列。
            path.pop()
            used[i] = False 
    dfs_inner(values)
    return result 
        
def illegal(result)->bool:            # 模拟入栈、出栈，判断出栈顺序是否合理.
    stack_ = []
    for i in values:   # 入栈
        stack_.append(i)
        while stack_!=[] and stack_[-1]==result[0]: # 栈顶==出栈值，栈和出栈序列一起弹出;
            stack_.pop()
            result.pop(0)
    if stack_==[]: 
        return True 
    else: return False 

if __name__=='__main__':
    nums = int(input())
    values = input().split(' ')

    result_all = sorted(dfs(values,nums))
    for i in result_all:
        print(' '.join(i))