张芷铭的个人博客

递归模拟栈操作，每个状态可选择「入栈」或「出栈」，生成所有合法序列。

问题

自然数 1, 2, …, N（1 ≤ N ≤ 100）依次入栈，找出所有合法出栈序列。

解决思路

递归模拟两种操作：

操作条件
入栈还有元素未入栈
出栈栈非空

递归终止条件：序列长度等于 N。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def generate_sequences(n, stack=[], sequence=[], result=[], in_stack=1):
    """
    生成所有合法出栈序列

    :param n: 总数
    :param stack: 当前栈状态
    :param sequence: 已生成的出栈序列
    :param result: 结果列表
    :param in_stack: 下一个要入栈的数字
    """
    if len(sequence) == n:
        result.append(sequence[:])  # 必须拷贝
        return

    # 入栈操作
    if in_stack <= n:
        stack.append(in_stack)
        generate_sequences(n, stack, sequence, result, in_stack + 1)
        stack.pop()  # 回溯

    # 出栈操作
    if stack:
        sequence.append(stack.pop())
        generate_sequences(n, stack, sequence, result, in_stack)
        stack.append(sequence.pop())  # 回溯

# 使用示例
result = []
generate_sequences(3, result=result)
for seq in result:
    print(seq)
# 输出：[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]

关键点

为什么用 sequence[:] 而非 sequence？

result.append(sequence) 添加的是引用，所有元素指向同一个列表对象。后续修改会影响已添加的结果。

sequence[:] 或 list(sequence) 创建浅拷贝，由于元素是 int（不可变），等同于值复制。

回溯模式：

  • 入栈后 stack.pop() 恢复状态
  • 出栈后 stack.append(sequence.pop()) 恢复状态

Comments