AcWing 92. 递归实现指数型枚举
原题链接
简单
作者:
粘豆包儿
,
2022-02-23 19:48:45
,
所有人可见
,
阅读 183
import java.util.*;
/**
* 92.递归实现指数型枚举
* @author xiaoshiguang
* @instruction:
* 2022-2-22 20:02:55
*/
public class Main {
public static int N = 16;
public static int[] state = new int[N];//状态,判断每一位是不是已经选了,选了的是1,没选的是2,空着的是0
static int n;
public static int[][] ways = new int[1 << 15][16];// 1<<15是2的15次方
public static ArrayList<ArrayList<Integer>> arraylist = new ArrayList<ArrayList<Integer>>();
private static void dfs(int u) {
ArrayList<Integer> arrayList2 = new ArrayList<Integer>();
//先找临界值
if(u > n) {
for(int i = 1;i<=n;i++) {
if(state[i] == 1) {
// System.out.print(i+" ");
arrayList2.add(i);
}
}
arraylist.add(arrayList2);
// System.out.println();
return;
}
state[u] = 2;//第二个分支不选
dfs(u + 1);
state[u] = 0;//恢复现场
state[u] = 1;//第二个分支选
dfs(u+1);
state[u] = 0;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
dfs(1);
for(int i = 0;i<arraylist.size();i++) {
for(int j = 0;j<arraylist.get(i).size();j++) {
System.out.print(arraylist.get(i).get(j)+" ");
}
System.out.println();
}
}
}