题解 | 全排列

//第一次提交之后超时了，莫名其妙的

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
  	//全局变量是静态的，也可以将used[]放进参数中去，那样就不需要回溯了。
    static boolean used[] = new boolean[10];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] list = new int[n];
            dfs(n,0,list);
        }
    }
    public static void dfs(int n, int cur,int[] list) {
        if(cur == n) {
            for(int num :list) {
                System.out.print(num +" ");
            }
            System.out.print("\n");
            return;
        }
        for(int i=1;i<=n;i++) {
            if(!used[i]) {
                list[cur] = i;
                used[i] = true;
                dfs(n,cur+1,list);
                used[i] = false;
            }
        }
        return;
    }
}

第一次提交之后超时了，莫名其妙的

思路

对每个位置进行枚举，并将其使用状态记录下来，一直向后推，一直到所有位置都填满。

然后使用回溯，清理状态，然后寻找下一个排列。