java---DFS算法---排列数字（每日一道算法2022.8.19）

题目
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法
现在，请你按照字典序将所有的排列方法输出

输入
3
1
2

输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1
2
3
4
5
6
7

public class DFS_排列数字 {
    //初始化，n记得在外面初始化啊，要不然dfs里调不到
    public static int N = 10, n;
    public static int[] path = new int[N];
    public static boolean[] st = new boolean[N];

    public static void main(String[] args) {
        //初始化
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        dfs(0);
    }
    //这里的核心思想就是找到未被使用的数，例如第一个数为1，那么第二个数只能为2或者3，第二个数为2，第三个数就只能为3，以此类推
    //用st，boolean数组标记当前数字有没有被使用过
    //path数组记录下当前这一串数，最后当u==n说明没有数可用了，探底了，就输出path的内容
    //path不用每次清空，因为每次path都会被覆盖
    public static void dfs(int u) {
        if (u == n) {
            for (int i = 0; i<n; i++) {
                System.out.print(path[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 1; i<=n; i++){
            if (!st[i]) {
                path[u] = i;
                st[i] = true;
                dfs(u+1);
                st[i] = false;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

声明：算法思路来源为y总，详细请见https://www.acwing.com/
本文仅用作学习记录和交流