题解 | #火车进站#

# 初始化一个空列表，用于存储所有可能的出站顺序
res = []

# 定义深度优先搜索函数
# wait: 等待进站的火车列表
# stack: 当前在站内的火车栈（后进先出）
# out: 已经出站的火车列表
def dfs(wait, stack, out):
    # 当等待进站和站内火车都为空时，表示所有火车都已出站
    # 此时，将出站顺序添加到结果列表中
    if not wait and not stack:
        res.append(' '.join(map(str, out)))
    
    # 如果还有火车等待进站
    # 则选择一辆火车进站（入栈），并继续搜索
    if wait: 
        dfs(wait[1:], stack + [wait[0]], out)
    
    # 如果站内还有火车（栈不为空）
    # 则可以选择一辆火车出站（出栈），并继续搜索
    if stack: 
        dfs(wait, stack[:-1], out + [stack[-1]])

# 无限循环，直到捕获到异常（例如输入结束）
while True:
    try:
        # 读取火车总数和进站编号列表
        n, nums = int(input()), list(map(int, input().split()))
        
        # 调用深度优先搜索函数，从初始状态开始搜索所有可能的出站顺序
        dfs(nums, [], [])
        
        # 对所有可能的出站顺序进行排序，并输出
        for i in sorted(res):
            print(i)
        
        # 清空结果列表，为下一组输入做准备（如果有的话）
        res.clear()
    
    except:
        # 捕获异常，跳出循环（通常是因为输入结束）
        break