题解 | #火车进站#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer bu = new StringBuffer();
        String a, b;
        int i = 0, j, l, n = 0, sum = 0;
        try {
            a = in.readLine();
            b = in.readLine();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        char[] chs = a.toCharArray();
        int[] train, seq;
        int[][] outTrain;
        l = chs.length;
        while (i < l) {
            n *= 10;
            n += chs[i] - '0';
            i++;
        }
        train = new int[n];
        outTrain = new int[9000][n];
        chs = b.toCharArray();
        parse(chs, train);
        Stack<Integer> station = new Stack<>();
        seq = new int[n];
        sum = approach(outTrain, train, seq, station, 0, 0, 0);//递归出站
//        System.out.print(sum);
        Arrays.sort(outTrain, 0, sum, new Comparator<int[]>() {//排序算法
            @Override
            public int compare(int[] o1, int[] o2) {
                int v = 0, len1 = o1.length, exc = 0;
                while (v < len1) {
                    exc = o1[v] - o2[v];
                    if (exc != 0) break;
                    else v++;
                }
                return exc;
            }
        });
        i = 0;
        while (i < sum) {//输出结果
            j = 0;
            while (j < n) {
                if (j != n - 1) bu.append(outTrain[i][j]).append(" ");
                else bu.append(outTrain[i][j]).append("\n");
                j++;
            }
            i++;
        }
        System.out.print(bu);
    }

    /**
     * 车出战的递归方法
     * @param outTrain
     * @param train     火车数组，从0开始存放火车编号
     * @param seq       出站数组，从0开始存放火车编号
     * @param station   火车站，栈结构
     * @param i         火车数组索引
     * @param j         出站数组索引
     * @param option
     * @return
     */
    private static int approach(int[][] outTrain, int[] train, int[] seq,
                                Stack<Integer> station, int i, int j, int option) {
        int num, l = train.length, k;
        if (station.isEmpty() &&
                i == l) {//火车站没有火车，并且所有火车都已出发，火车数组遍历完
            k = 0;
            while (k < l) {
                outTrain[option][k] = seq[k];//出站数组放入总数组中
                k++;
            }
            return ++option;
        } else {
            if (!station.isEmpty()) {//火车站不为空，可以出站
                num = station.pop();
                seq[j] = num;
                option = approach(outTrain, train, seq, station, i, j + 1, option);
                station.push(num);//回溯
            }
            if (i < l) {//还有火车没有出发，则可以进入火车站
                num = train[i];
                station.push(num);
                option = approach(outTrain, train, seq, station, i + 1, j, option);
                station.pop();//回溯
            }
        }
        return option;
    }

    private static void parse(char[] chs, int[] train) {
        int l = chs.length, i = 0, j = 0, n = 0;
        while (i < l) {
            if (chs[i] == ' ') {
                train[j++] = n;
                n = 0;
                i++;
                continue;
            }
            n *= 10;
            n += chs[i] - '0';
            if (i == l - 1) train[j] = n;
            i++;
        }
    }
}