题解 | #火车进站#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static List<String> res = new
    ArrayList<>();   //存放结果，也就是所有可能的出站序列

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            res.clear();
            int n = in.nextInt();//火车的数量
            int[] trains = new int[n];//存放火车编号
            Stack<Integer> station = new Stack<>();//用栈表示车站，只能先进后出
            for (int i = 0; i < n; i++) {
                trains[i] = in.nextInt();
            }
            trainOut(trains, 0, station, "", 0);
            Collections.sort(res);
            for (String s : res) {
                System.out.println(s);
            }
        }
        in.close();
    }

    public static void trainOut(int[] trains, int in, Stack<Integer> station,
                                String resTemp, int out) {
        if (out ==
                trains.length) {   //out表示已经出站的火车数量。当所有火车出站时，表示一个出站序列完成，将其添加到结果中
            res.add(resTemp);
        }
        if (!station.empty()) {  //当车站还有火车时
            int train = station.pop();  //出站一辆火车
            trainOut(trains, in, station, resTemp + train + " ",
                     out + 1);//该出站火车添加到当前出站序列，出站火车数量+1
            station.push(train);
        }
        if (in < trains.length) { //当还有火车未进站时
            station.push(trains[in]);//进站一辆火车
            trainOut(trains, in + 1, station, resTemp, out);//已进站火车数量+1
            station.pop();
        }
    }
}