题解 | #火车进站#

# 这道题目考了俩个 考点：
# 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))