华为火车进站问题创新解法

看了题解和讨论区都是用传统的进出栈来求解的，我这里提出一种新的思路，运用递归的方法：
1）我们从对车的操作来考虑，构造一个对车进行操作的标记序列，例如[1,2,2,1]就代表1号车进站，2号车进站，2号车出站，1号车出站的一个操作流程，从这里我们不难看出，序列中第一次出现的序号代表该序号进站，第二次出现代表出站。
2）这里我们着重考虑最后一辆车进出站的情况，不难发现最后一辆车进站发生在前一辆进站之后的任意时刻都满足条件，而最后一辆车进站后由于没有车还能进站因此必须立即出站，因此在操作序列中，最后一辆车的序号必是连续的。
3）有了以上两点结论后我们便可以构造递归函数：

def cal(x,s):
    if x == 1:
        return [[s[0],s[0]]]    #只有一辆车时递归终止
    else:
        res = []
        for i in cal(x-1,s[0:x-1]):
            add = i.index(s[x-2])    #获得x-1辆车的操作序列中第x-1辆车编号第一次出现时的下标
            for j in range(add+1,len(i)+1):    #在第x-1辆车编号第一次出现之后的任意位置均可插入连续的第x辆车编号获得新序列
                temp = i[:]
                temp.insert(j,s[x-1])
                temp.insert(j,s[x-1])
                res.append(temp)
        return res

函数的输入参数x和s分别表示的是车的数量和进站的编号序列，递归的重点是车只有一辆时，只有进站出站一种排列方式，对于车有x辆时，由开头得出的两个结论，x辆车时的操作序列可以由x-1辆车时的操作序列中插入连续的第x辆车编号来获得。
现在我们得到了操作序列后我们需要由操作序列得到出站序列，显然我们只要把每辆车编号的第一次出现删除即可

while True:
    try:
        n = int(input())
        sou = [int(x) for x in input().split()]
        ans = cal(n,sou)    #得到操作序列
        for i in ans:
            for j in range(1,n+1):
                i.remove(j)    #删除每辆车编号的第一次出现
        ans.sort()
        for i in ans:
            print(' '.join([str(x) for x in i]))
    except:
        break