题解 | #火车进站#

import java.util.*;

public class Main {
    
    static int N;
    static List<Station> list = new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] trains = new int[N = in.nextInt()];
        fill(trains, in);
        // Station是自己定义的一个数据结构 用于存储列车出站顺序 排序 输出等
        dfs(trains, 0, 0, new LinkedList<Integer>(), new Station());
        Collections.sort(list);
        list.forEach(System.out::println);
    }

    static void dfs(int[] trains, int index, int outCount, LinkedList<Integer> stack, Station station) {
        // 如果所有列车都出站了 添加这次出站顺序
        if (outCount == N) {
            list.add(station);
        } else {
            // 列车出站 
            if (!stack.isEmpty()) {
                int train = stack.pop();
                dfs(trains, index, outCount + 1, stack, station.clone().in(train));
                // 中断恢复
                stack.push(train);
            }
            // 列车进站
            if (index < N) {
                stack.push(trains[index]);
                dfs(trains, index + 1, outCount, stack, station);
                // 中断恢复
                stack.pop();
            }
        }
    }

    static void fill(int[] arr, Scanner in) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.nextInt();
        }
    }

    static class Station implements Comparable<Station> {
        
        int[] trains = new int[N];
        int size = 0;

        Station() {}

        Station(int[] trains, int size) {
            this.trains = trains;
            this.size = size;
        }

        public Station in(int train) {
            this.trains[size++] = train;
            return this;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < trains.length; i++) {
                sb.append(trains[i]).append(" ");
            }
            return sb.toString();
        }

        @Override
        public int compareTo(Station station) {
            for (int i = 0; i < this.trains.length; i++) {
                if (this.trains[i] != station.trains[i]) {
                    return this.trains[i] - station.trains[i];
                }
            }
            int n = this.trains.length;
            return this.trains[n - 1] - station.trains[n - 1];
        }

        @Override
        public Station clone() {
            int[] trains = Arrays.copyOf(this.trains, N);
            return new Station(trains, size);
        }
    }
}