题解 | #火车进站#DFS+STACK

首先构造出入栈的顺序序列, 需要满足两个条件

1. 第一个必须是i(入栈)
2. i的个数必须大于等于o(出栈)的个数 在每一次得到合法顺序之后使用栈模拟 得到结果

N = int(input())
a = list(map(int, input().split()))
res = []
def dfs(order, inum, onum):
    if len(order)==N*2:
        stack = []
        tmp = []
        tmpa = a.copy()
        for o in order:
            if o == 'i':
                stack.append(tmpa.pop(0))
            else:
                tmp.append(str(stack.pop()))
        res.append(" ".join(tmp))
        return 
    if inum<N: dfs(order+['i'], inum+1, onum)
    if onum<N and onum<inum: dfs(order+['o'], inum, onum+1)
dfs(['i'], 1, 0)
res.sort()
for r in res:
    print(r)