题解 | 火车进站

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static List<String> results = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] num = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = in.nextInt();
        }
        dfs(0, new ArrayDeque<>(), new ArrayList<>(), num);
        // 按照字典序排序（虽然我们的DFS策略已经保证了顺序，但显式排序更稳妥）
        Collections.sort(results);

        // 输出所有结果
        for (String seq : results) {
            System.out.println(seq);
        }

    }
    /**
     * 深度优先搜索所有可能的出站序列
     * @param index   下一辆要入站的火车在数组a中的索引
     * @param stack   当前站内的火车栈
     * @param output  已经出站的火车序列
     * @param a       原始的入站序列
     */
    private static void dfs(int index, Deque<Integer> stack, List<Integer> output,
                            int[] a) {
        // 递归终止条件：所有火车都已入站且出站
        if (index == a.length && stack.isEmpty()) {
            // 将当前的出站序列转换为字符串并添加到结果列表
            StringBuilder sb = new StringBuilder();
            for (int number : output) {
                sb.append(number).append(" ");
            }
            // 删除末尾多余的空格
            if (sb.length() > 0) {
                sb.setLength(sb.length() - 1);
            }
            results.add(sb.toString());
            return;
        }

        // 选择1：如果栈不为空，可以让栈顶的火车出站
        // 优先考虑出栈，可以保证字典序从小到大
        if (!stack.isEmpty()) {
            int top = stack.pop();
            output.add(top);

            dfs(index, stack, output, a);

            // 回溯：恢复现场，以便尝试其他选择
            output.remove(output.size() - 1);
            stack.push(top);
        }
        // 选择2：如果还有火车未入站，可以让下一辆火车入站
        if (index < a.length) {
            stack.push(a[index]);
            dfs(index + 1, stack, output, a);

            // 回溯：恢复现场
            stack.pop();
        }
    }
}