递归+栈 | HJ77 火车进站

# 最优解
res = []
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)
    except:
        break

思路：有两个状态（出栈和不出栈）且随深度遍历不同选择，符合递归类型。先写出出栈和不出栈的递归代码，递归结束条件不确定时，可以调试时观察什么情况下需要记录遍历路径结果。

递归函数的参数如何确定？本题随着递归深度变化，1. 需要一个记录入站火车情况的栈变量；2. 出栈路径记录值会变化，每获取一个有效结果值就加入到全局变量res中；3. 还需要标志剩余待进栈火车的记录值

用时：2h