题解 | #火车进站#
火车进站
https://www.nowcoder.com/practice/97ba57c35e9f4749826dc3befaeae109
# 这道题目考了俩个 考点：
# 1、dfs回溯算法 写全排列 参考 leecode 46. 全排列
# 2、判断是否为合法栈输出 参考 leecode 946. 验证栈序列
# 我在这里直接用两个方法 封装起来了。
def dfs(values,nums):
path,result,used = [],[],[False for _ in range(nums)]
def dfs_inner(values):
if len(path)==nums:
if illegal(path.copy()): # 把判断是否合法 嵌入回溯算法中，不然用两个方法前后相衔接的方式写，会超时。
result.append(path.copy())
for i in range(nums):
if used[i]==True:
continue
used[i] = True
path.append(values[i])
dfs_inner(values) # 排列和组合这里有区别，这里是排列。
path.pop()
used[i] = False
dfs_inner(values)
return result
def illegal(result)->bool: # 模拟入栈、出栈，判断出栈顺序是否合理.
stack_ = []
for i in values: # 入栈
stack_.append(i)
while stack_!=[] and stack_[-1]==result[0]: # 栈顶==出栈值，栈和出栈序列一起弹出;
stack_.pop()
result.pop(0)
if stack_==[]:
return True
else: return False
if __name__=='__main__':
nums = int(input())
values = input().split(' ')
result_all = sorted(dfs(values,nums))
for i in result_all:
print(' '.join(i))
