题解 | 全排列

import java.io.*;
import java.util.*;

public class Main {
     /**
     * 主方法，程序的入口点
     *
     * @param args 命令行参数
     * @throws IOException 可能抛出IO异常
     */
    public static void main(String[] args) throws IOException {
        // 使用BufferedReader从标准输入读取数据
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 使用PrintWriter向标准输出写入数据
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        // 读取整数n，并去除可能的空白字符
        int n = Integer.parseInt(br.readLine().trim());

        // 初始化一个长度为n的数组，用于存储排列结果
        int[] track = new int[n];
        // 初始化一个长度为n+1的布尔数组，用于标记数字是否已被使用
        boolean[] used = new boolean[n + 1];

        // 调用回溯方法生成全排列
        backtrack(n, 0, track, used, out);
        // 刷新输出流，确保所有数据都被写出
        out.flush();
        // 关闭输出流
        out.close();
        // 关闭输入流
        br.close();


    }

    /**
     * 回溯法生成全排列
     *
     * @param n     排列的数字范围，1到n
     * @param depth 当前递归的深度，即已经确定的前几个数字的数量
     * @param track 当前排列的路径，存储已经确定的数字序列
     * @param used  标记数组，记录数字是否已经在当前排列中使用过
     * @param out   用于输出结果的打印流
     */
    private static void backtrack(int n, int depth, int[] track, boolean[] used, PrintWriter out) {
        // 如果当前深度等于n，说明已经生成了一个完整的排列
        if (depth == n) {
            // 输出当前排列
            for (int i = 0; i < n; i++) {
                // 如果是最后一个数字，直接输出，否则输出数字加空格
                out.print(track[i] + (i == n - 1 ? "" : " "));
            }
            // 换行，准备输出下一个排列
            out.println();
            // 返回上一层递归
            return;
        }

        // 遍历所有可能的数字
        for (int i = 1; i <= n; i++) {
            // 如果数字i还没有被使用过
            if (!used[i]) {
                // 标记数字i为已使用
                used[i] = true;
                // 将数字i放入当前深度的位置
                track[depth] = i;

                // 递归处理下一个位置
                backtrack(n, depth + 1, track, used, out);

                // 回溯，撤销选择，将数字i标记为未使用，以便尝试其他可能性
                used[i] = false;
            }
        }
    }
}