1.DFS实现指数型枚举
package lanqiao;
import java.util.Scanner;
public class _92_dfs实现指数型枚举 {
static int n;
static int[] a=new int[20];
static boolean[] used=new boolean[20];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i =1; i <=n; i++) {
//枚举每次的target坑位
dfs(1,1,i);
}
}
//当前枚举到pos个坑 ,上一个坑填的是start-1,一共要填tar个坑
static void dfs(int pos,int start,int target) {
if(pos==target+1) {
for (int i = 1; i <=target; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
for (int i = start; i <=n; i++) {
if(!used[i]) {
used[i]=true;
a[pos]=i;
dfs(pos+1,i+1,target);
a[pos]=0;
used[i]=false; //回溯
}
}
}
}
2. 二进制优化实现指数型枚举
package lanqiao;
import java.util.Scanner;
public class _92_二进制优化实现指数型枚举 {
/*
* 用一个二进制数表示选了哪些数,替代之前的a[20]数组
其中 state |= 1 << (i - 1) 代表状态的改变,选了i这个数
state ^= 1 << (i - 1) 代表状态的还原,还原没选i这个数的状态
*/
/*
* 例中n=3,即
000 -> \n
001 -> 1
010 -> 2
100 -> 3
011 -> 1 2
101 -> 1 3
110 -> 2 3
111 -> 1 2 3
*/
static int n;
static boolean[] used=new boolean[20];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i =1; i <=n; i++) {
//枚举每次的target坑位
dfs(1,1,i,0);
}
}
//当前枚举到pos个坑 ,上一个坑填的是start-1,一共要填tar个坑 ,state 是每一个状态
static void dfs(int pos,int start,int target ,int state) {
if(pos==target+1) {
for (int i =0; i <n; i++) {
// 用指针j遍历二进制数state中的每一位
if((state>>i&1)==1) {
System.out.print(i+1+" ");
}
}
System.out.println();
}
for (int i = start; i <=n; i++) {
if(!used[i]) {
used[i]=true;
state|=1<<(i-1); //state |= 1 << (i - 1) 代表状态的改变,选了i这个数
dfs(pos+1,i+1,target,state);
state^=1<<(i-1);//state ^= 1 << (i - 1) 代表状态的还原,还原没选i这个数的状态
used[i]=false;
}
}
}
}
3. 状态压缩递归
package lanqiao;
import java.util.Scanner;
public class _92_状态压缩递归 {
static int n;
static boolean[] used=new boolean[20];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dfs(0,0);
}
//,state 是每一个状态
static void dfs(int u ,int state) {
if(u==n) {
for (int i =0; i <n; i++) {
// 用指针j遍历二进制数state中的每一位
if((state>>i&1)==1) {
System.out.print(i+1+" ");
}
}
System.out.println();
return;
}
dfs(u+1,state); //不使用u这个数
dfs(u+1,state|(1<<u));//使用u这个数
}
}