题解 | #火车进站#

Key

• 回溯
• 索引每到一个序号时都有进栈和出栈两种情况：进栈时tmp_a添加，tmp_b不变；出栈时tmp_a出栈，添加到tmp_b中
• 每到栈内剩余情况的用tmp_a表示，出栈情况用tmp_b表示，当索引到最后一个进栈火车后，dfs结束，tmp_b+tmp_a倒序未最终的出栈情况

import sys
import heapq

N = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().split()))

result = []
def dfs(nums, tmp_a, tmp_b, i, result):
    if i == N:
        result.append(tmp_b + tmp_a[::-1])
        return

    tmp_a.append(nums[i])
    dfs(nums, tmp_a, tmp_b, i + 1, result)   # 进栈
    tmp_a.pop()

    if tmp_a:
        tmp_ = tmp_a.pop()
        tmp_b.append(tmp_)
        dfs(nums, tmp_a, tmp_b, i, result)  # 出栈
        tmp_b.pop()
        tmp_a.append(tmp_)

dfs(nums, [], [], 0, result)
result.sort()   # 能够进行字典排序

for res in result:
    res = map(str, res)
    print(' '.join(res))