求集合的所有子集
程序员文章站
2024-03-21 15:02:46
...
转载博客:https://blog.csdn.net/yanerhao/article/details/77075462
我们知道一个一个包含n个元素的集合一共有2^n个子集,例如:
集合S包含三个元素{a, b, c},则它的所有子集为:{ }(空集), {a}, {b}, {c}, {a, b}, {a, c}, {b, c} 和{a, b, c}。
这里先用位操作的思路来求解,具体方法:用2进制Bit位来标记集合中的某个元素是否被选中,1代表选中,0代表未选中。例如集合{a, b, c}的所有子集可如下表示:
{}(空集) 0 0 0
{a} 0 0 1
{b} 0 1 0
{c} 1 0 0
{a, b} 0 1 1
{a, c} 1 0 1
{b, c} 1 1 0
{a, b, c} 1 1 1
分析中也可以看出一个包含N个元素的集合S有2^N个子集,非常容易想到的方法就是遍历0~2^N-1的所有整数,并转化为二进制,按以上思路输出所有子集:
代码:
void get_allsubset(int a[],int n){
int mask=0;
int start=0;
int end=(1<<n)-1;
int i=0;
bool isnull;
for(mask=start;mask<=end;mask++){
isnull=1;
for(i=0;i<n;i++)
if((1<<i)&mask){
isnull=0;
cout<<a[i]<<" ";
}
if(isnull)cout<<"!";
cout<<endl;
}
}
上一篇: 求素数个数
下一篇: Android 系统启动