一.解题思路

使用深度优先搜索，递归式的先找到一组满足题目要求的排列顺序并输出。
输出后在回溯进行下一次递归找到符合题目要求的排列顺序，找到则进行输出，未找到则退出递归。

二.Quesion & Answer

dfs()函数中的return 语句省略为什么也可以AC

用数据模拟:当n = 8，u = 9时，
此时 dfs() 函数会输出一组排列方案，并进入for循环，但是此时却不会执行if语句里面的dfs()函数，
原因是在之前从u = 1到 u = 8的过程中，st[1] 到 st[8] 的值会被赋为1, if 判断不会成立。
当 for 循环语句执行完之后,会退出 dfs() 函数，相当于执行了 return 语句。

三.AC代码

import java.util.*;

class Main{
    static int n = 0;
    static int q[] = new int[10];
    static int st[] = new int[10];

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        dfs(1);
    }

    static void dfs(int x){
        if(x > n){
            for(int i = 1;i <= n;i ++){
                System.out.print(q[i]+" ");
            }
            System.out.println();
            return ;
        }
        for(int i = 1;i <= n;i ++)
        {
            if(st[i] == 0)
            {
                st[i] = 1;
                q[x] = i;
                dfs(x+1);
                st[i] = 0;
            }
        }
    }
}