子集生成简介
给定n个数字，枚举出所有可能的子集
例如给定n=3，枚举出{1，2，3}所有可能的子集
{1}、{2}、{3}、{1,2}、{1,2,3}、{2,3}
增量构造法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <cstdio> const int maxn = 100 + 10; //打印0~n-1的所有子集 //按照递增顺序就行构造子集 防止子集的重复 void GenSubsetIncr(int *arr, int n, int cur){ for(int i = 0; i < cur; i++) printf("%d ", arr[i]); printf("\n"); int s = cur ? arr[cur-1] + 1 : 0; //确定当前元素的最小可能值 for(int i = s; i < n; i++){ arr[cur] = i; GenSubsetIncr(arr, n, cur+1); } } int main(){ int n, arr[maxn]; scanf("%d", &n); GenSubsetIncr(arr, n, 0); return 0; } |
位向量法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
// 1~n 的所有子集：位向量法 #include <cstdio> const int maxn = 100 + 10; using namespace std; int bits[maxn];//位向量bits[i] = 1,当且仅当i在子集 A 中 void GenSubsetBit(int n,int cur){ if(cur == n){ for(int i = 0; i < cur; i++) if(bits[i]) printf("%d ",i); printf("\n"); return; } bits[cur] = 1; GenSubsetBit(n,cur + 1); bits[cur] = 0; GenSubsetBit(n,cur + 1); } int main() { int n; scanf("%d", &n); GenSubsetBit(n,0); return 0; } |
二进制法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// 0 ~ n-1的所有子集：二进制法枚举0 ~ n-1的所有子集 #include <cstdio> const int maxn = 100 + 10; using namespace std; void GenSubset01(int n,int cur){ //这一步其实就是判断 cur 的二进制的各个位上是不是1，如果是1,就输出对应的那个位置(位置从0开始) for(int i = 0; i < n; i++) if(1 & (cur >> i)) printf("%d ",i); printf("\n"); } int main(int argc, char const** argv) { int n; scanf("%d",&n); for(int i = 0; i < (1 << n); i++) GenSubset01(n,i);//枚举各子集对应的编码 0,1,2...pow(2,n) - 1 return 0; } |
