题解 | #火车进站#

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String nextLine = in.nextLine();
            if (Objects.isNull(nextLine) || nextLine.equals("")) {
                break;
            }
            // 可执行车辆数
            int n = Integer.parseInt(nextLine);
            // 进站序列
            Stack<String> trainStack = new Stack<>();
            String trainIndex = in.nextLine();
            String[] trains = trainIndex.split(" ");
            for (int i = n - 1; i >= 0; i--) {
                trainStack.push(trains[i]);
            }
            // 解决方案
            List<String> solutions = new ArrayList<>();
            // 当前车站车辆数
            Integer total = 0;
            dfs("", solutions, new Stack<>(), trainStack);
            solutions.sort(String::compareTo);
            solutions.forEach(item -> System.out.println(item.substring(1)));
        }
    }

    /**
     * @param solution 当前出站方案
     * @param solutions 记录出站的车辆
     * @param train1 待出站的车辆
     * @param train2 待进站的车辆
     */
    private static void dfs(String solution, List<String> solutions, Stack<String> train1, Stack<String> train2) {
        // 都出光了，那么就退出递归
        if (train1.isEmpty() && train2.isEmpty()) {
            solutions.add(solution);
            return;
        }
        // 如果出站车辆为空，只能进站
        if (train1.isEmpty()) {
            inTrain(solution, solutions, train1, train2);
        }
        // 如果进站车辆为空，只能出站
        if (train2.isEmpty()) {
            // 先拷贝一份待进站和车辆和待出站的车辆
            Stack<String> train1Copy = new Stack<>();
            train1Copy.addAll(train1);
            Stack<String> train2Copy = new Stack<>();
            train2Copy.addAll(train2);
            String train = train1Copy.pop();
            solution = solution + " " + train;
            dfs(solution, solutions, train1Copy, train2Copy);
        }
        // 如果出站车辆和进站车辆都不为空，则可以执行先出站，或者执行先进站
        if (!train1.isEmpty() && !train2.isEmpty()) {
            inTrain(solution, solutions, train1, train2);
            outTrain(solution, solutions, train1, train2);
        }
    }

    /**
     * 执行进站
     *
     * @param solution
     * @param solutions
     * @param train1
     * @param train2
     */
    public static void inTrain(String solution, List<String> solutions, Stack<String> train1, Stack<String> train2) {
        // 先拷贝一份待进站和车辆和待出站的车辆,不影响原先的栈
        Stack<String> train1Copy = new Stack<>();
        train1Copy.addAll(train1);
        Stack<String> train2Copy = new Stack<>();
        train2Copy.addAll(train2);
        String train = train2Copy.pop();
        train1Copy.push(train);
        dfs(solution, solutions, train1Copy, train2Copy);
    }

    /**
     * 执行出站
     *
     * @param solution
     * @param solutions
     * @param train1
     * @param train2
     */
    public static void outTrain(String solution, List<String> solutions, Stack<String> train1, Stack<String> train2) {
        // 先拷贝一份待进站和车辆和待出站的车辆,不影响原先的栈
        Stack<String> train1Copy = new Stack<>();
        train1Copy.addAll(train1);
        Stack<String> train2Copy = new Stack<>();
        train2Copy.addAll(train2);
        String train = train1Copy.pop();
        solution = solution + " " + train;
        dfs(solution, solutions, train1Copy, train2Copy);
    }
}