题解 | #火车进站#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int[] trains = new int[num];
        for(int i = 0; i < num; i++){
            trains[i] = in.nextInt();
        }
        in.close();

        List<String> res = new ArrayList<>();
        Stack<Integer> station = new Stack<>();
        dfs(res,"",trains,station,0,0);
        Collections.sort(res);
        for(String s : res){
            System.out.println(s);
        }
    }

    private static void dfs(List<String> res,String tmp, int[] trains, Stack<Integer> station, int in, int out){
        if(out == trains.length){   //所有火车均已出站
            res.add(tmp);
        }

        if(!station.empty()){   //车站不空，尚有火车没有出站
            int train = station.pop();
            dfs(res,tmp + train + " ",trains,station,in,out + 1);
            station.push(train);
        }

        if(in < trains.length){ //还有火车没有进站
            station.push(trains[in]);
            dfs(res,tmp,trains,station,in + 1,out);
            station.pop();
        }
    }
}