题解 | #火车进站#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            // 结果列表
            List<String> ans = new ArrayList<>();
            // 记录站内火车
            Stack<Integer> stack = new Stack<>();
            // 火车出站序列号
            List<Integer> outList = new ArrayList<>();
            // 火车数量
            int n = in.nextInt();
            int[] trains = new int[n];
            for (int i = 0; i < n; i++) {
                trains[i] = in.nextInt();
            }
            helper(trains, 0 ,0, stack, "", ans);

            



            Collections.sort(ans);
            for (String str : ans) {
                System.out.println(str);
            }
        }
    }

    /**
    * @param trains 全部火车
    * @param i 入栈火车数量
    * @param j 出站火车数量
    * @param stack 站内火车栈
    * @param out 一次结果
    * @param ans 总结果
    */
    public static void helper(int[] trains, int i, int j, Stack<Integer> stack, String out, List<String> ans) {
        if (j == trains.length) {
            // 或者全部出站
            ans.add(out);
        }
        // 火车有两种情况： 出站或入站
        // 出站
        if (!stack.isEmpty()) {
            int tmp = stack.pop();
            helper(trains, i, j + 1, stack, out + tmp + " ", ans);
            // 恢复现场
            stack.push(tmp);
        }
        // 入站
        if (i < trains.length) {
            stack.push(trains[i]);
            helper(trains, i + 1, j, stack, out, ans);
            // 恢复现场
            stack.pop();
        }
    }
}