子集生成和组合问题
一、组合和全排列的区别
全排列中每一个排列都是有顺序的，而且每个元素都要出现。
组合是将所给n个元素中选择任意个元素成为一个组合，每一个组合没有顺序。
二、思路分析
设有一个包含n个元素的集合从a0、a1、a2 ......an-1，由集合的概念我们可以知道，n个元素的集合共有2n个子集
如果我们把2n用二进制表示，那么一共有n位，每一位代表一个元素，0代表没有这个元素，1代表有这个元素。
所以从数字1-2n，每一个数字对应的二进制，就是一个子集，即一种组合。
通过处理每个数字中的1，打印所有的子集
三、代码实现
#include<iostream>
using namespace std;
void print_subset(int n)
{
for(int i=0;i<(1<<n);i++)//1左移n位就是2的n次方
{
for(int j=0;j<n;j++)
{
if(i&(i<<j))//判断每一位是否是1
cout<<j<<" ";//这一位上是1就打印这一位
}
cout<<endl;
}
}
int main()
{
int n;
cin>>n;
print_subset(n);
return 0;
}
对于打印n个元素中任意m个数的组合，代码如下
#include<iostream>
using namespace std;
void print_subset(int n,int k)//n个元素，任意k个
{
for(int i=0;i<(1<<n);i++)
{
int num=0,kk=i;//num用来统计i中1的个数，kk用来处理i
while(kk)
{
kk=kk&(kk-1);//消除kk中最末尾的一个1
num++;//1的个数+1
}
if(num==k)//符合k个1
{
for(int j=0;j<n;j++)
{
if(i&(1<<j))
cout<<j<<" ";
}
cout<<endl;
}
}
}
int main()
{
int n,k;
cin>>n>>k;
print_subset(n,k);
return 0;
}
0
投递滴滴等公司9个岗位 >
开发你这个也没有项目啊
