题解 | 火车进站

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, new ArrayList<>(), new ArrayList<>(), result, a);
        Collections.sort(result, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                for (int i = 0; i < o1.size(); i++) {
                    int cmp = Integer.compare(o1.get(i), o2.get(i));
                    if (cmp != 0) {
                        return cmp;
                    }
                }
                return 0;
            }
        });
        for (List<Integer> list : result) {
            StringBuilder sb = new StringBuilder();
            for (int num : list) {
                sb.append(num).append(" ");
            }
            System.out.println(sb.toString().trim());
        }
    }

    private static void backtrack(int index, List<Integer> stack,
                                  List<Integer> path, List<List<Integer>> result, int[] a) {
        if (path.size() == a.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 尝试弹出栈顶元素
        if (!stack.isEmpty()) {
            int popped = stack.remove(stack.size() - 1);
            path.add(popped);
            backtrack(index, stack, path, result, a);
            path.remove(path.size() - 1);
            stack.add(popped);
        }
        // 尝试入栈下一个元素
        if (index < a.length) {
            int next = a[index];
            stack.add(next);
            backtrack(index + 1, stack, path, result, a);
            stack.remove(stack.size() - 1);
        }
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

输入处理：读取火车数量和入站顺序。

回溯函数：递归生成所有可能的出站顺序。每次递归处理两种选择：弹出栈顶元素或入栈下一个元素。

结果排序：使用自定义比较器对结果按字典序排序。

输出结果：将排序后的结果按格式输出。