题解 | #火车进站#

import java.util.*;
import java.util.Scanner;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int[] trains = new int[n];
            for (int i = 0; i < n; i++) {
                trains[i] = in.nextInt();
            }

            List<List<Integer>> result = new ArrayList<>();
            Deque<Integer> stack = new ArrayDeque<>();
            List<Integer> record = new ArrayList<>();

            backtrack(result, stack, trains, record, 0);

            // 排序并输出
            List<String> resultStrs = result.stream().map(integers -> {
                StringBuilder sb = new StringBuilder();
                integers.forEach((i) -> sb.append(i).append(' '));
                return sb.toString();
            }).sorted().collect(Collectors.toList());
            resultStrs.forEach(System.out::println);
        }
    }

    public static void backtrack(List<List<Integer>> result, Deque<Integer> stack, int[] trains,
                                 List<Integer> record, int index) {
        // 结束条件：所有车辆都入站过、车站内也没车辆、所有车辆都已经出站
        if (index == trains.length && stack.isEmpty() && record.size() == trains.length) {
            result.add(new ArrayList<>(record));
            return;
        }
        
        // 对于每一个状态，要么选择从车辆队列中入站，要么选择从车站中出站，
        // 如果选择入站，状态变化：车辆队列 index+1、站内车辆增加、出站的车辆不变
        // 如果选择出站，状态变化：车辆队列不变、站内车辆减少、出站的车辆增加

        // 出站，站内有车才能出站
        if (!stack.isEmpty()) {
            record.add(stack.pop());
            backtrack(result, stack, trains, record, index);
            stack.push(record.remove(record.size() - 1));
        }

        // 入站，车辆队列还有车才能入站
        if (index < trains.length) {
            stack.push(trains[index]);
            backtrack(result, stack, trains, record, index + 1);
            stack.pop();
        }
    }
}