题解 | 火车进站

没想到这个不起眼的小题还挺费心的。

1. 思路：模拟出入站（栈），并配合回溯。
2. 两处回溯：进站，出栈（进path）

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String[] trains = in.nextLine().split(" ");
        Stack<String> stack = new Stack<>();
        List<List<String>> allPath = new ArrayList<>();
        backtrace(trains, 0, stack, new ArrayList<>(), allPath);
        List<String> allPathStr = new ArrayList<>();
        for (List<String> path : allPath) {
            allPathStr.add(String.join(" ", path));
        }
        allPathStr.sort((o1, o2) -> o1.compareTo(o2));
        for (String s : allPathStr) {
            System.out.println(s);
        }
    }

    public static void backtrace(String[] trains, int idx, Stack<String> stack,
                                 List<String> path, List<List<String>> allPath) {
        if (path.size() == trains.length) {
            allPath.add(new ArrayList<>(path));
            return;
        }
        // 还有火车没进栈的快进
        if (idx < trains.length) {
            stack.push(trains[idx]);
            backtrace(trains, idx + 1, stack, path, allPath);
            stack.pop(); // 回溯
        }
        if (!stack.isEmpty()) {
            // 出栈
            String popTrain = stack.pop();
            path.add(popTrain);
            backtrace(trains, idx, stack, path, allPath);
            // 再次回溯
            path.remove(path.size() - 1);
            stack.push(popTrain);
        }
    }
}