AcWing 94. 递归实现排列型枚举—(Java)_DFS全排列模板
原题链接
简单
作者:
差一点睡死了
,
2021-02-10 13:56:24
,
所有人可见
,
阅读 390
DFS全排列模板
package lanqiao;
import java.util.Scanner;
public class _94_全排列 {
static int N=10;
static int n;
static int[] state=new int[N];//0表示还没放,1~n表示放了哪个数
static boolean[] used=new boolean[N];//true表示用过,false 表示没用过
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dfs(1);
}
static void dfs(int u) {
if(u>n) {//当每一层都完成,直接这一次结果
for (int i = 1; i <=n; i++) {
System.out.print(state[i]+" ");
}
System.out.println();
}
for (int i =1; i<=n; i++) {
if(!used[i]) {
state[u]=i;
used[i]=true;
dfs(u+1);
//回溯
state[u]=0;
used[i]=false;
}
}
}
}
大佬,请教一下,如果n=9,怎么优化时间复杂度啊,运行超时啊