子集生成（增量构造法、位向量法）子集生成（增量构造法、位向

一、增量构造法
给定n个数字，枚举出所有可能的子集
例如给定n=3，枚举出{1，2，3}所有可能的子集
{1}、{2}、{3}、{1,2}、{1,2,3}、{2,3}

文章图片
image.png 【子集生成（增量构造法、位向量法）】以下是java实现

public class sublist { public static void subset(int n, int A[], int cur) { for (int i = 0; i < cur; i++) System.out.printf("%d", A[i]); //打印当前集合 System.out.println(); int s; if (cur != 0) //如果cur=0，则从1开始，cur！=0，从A[cur - 1] + 1开始，由于数组坐标性质决定的 s = A[cur - 1] + 1; else s = 1; for (int i = s; i <= n; i++) { A[cur] = i; subset(n, A, cur + 1); //递归构造子集 }}public static void main(String[] args) { int n = 4; int A[] = new int [n]; sublist.subset(n, A, 0); }}

二、位向量法
构造一个位向量，只有当B[i] = 1时才打印该处位置的i值+1

文章图片
image.png

public class sublistB {public static void sublist(int n, int[] B,int cur) { if(cur == n) { for(int i = 0; i < n; i++) if(B[i] > 0) System.out.print(i+1+" "); //打印当前集合 System.out.println(); return; }B[cur] = 1; //选第cur个元素 sublist(n,B,cur+1); B[cur] = 0; //不选第cur个元素 sublist(n,B,cur+1); }public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] B = new int[n]; sublistB.sublist(n, B, 0); }}