二进制法(最简单,位运算符与&):
二进制中1代表选择,0代表不选择,用if(s&(1<<i))判断该输出哪个
注意如n=5时,输出的结果是0~4的子集,若要改成1~5的只需把输出的i+1即可
void print_subset(int n,int s)
{
for(int i=0;i<n;i++)
if(s&(1<<i))
printf("%d ",i);
printf("\n");
}
int main()
{
int n;
cin>>n;
for(int i=0;i<(1<<n);i++)
print_subset(n,i);
return 0;
}
位向量法:
递归回溯
n=5时,输出结果num=32
int b[maxn];
int num=0;
void print_subset(int n,int* b,int cur)
{
if(cur==n+1)
{
num++;
for(int i=1;i<=n;i++)
if(b[i]) printf("%d ",i);
printf("\n");
return ;
}
b[cur]=1;//选第cur个元素
print_subset(n,b,cur+1);
b[cur]=0;//不选第cur个元素
print_subset(n,b,cur+1);
}
int main()
{
int n;
cin>>n;
print_subset(n,b,1);
cout<<"num:"<<num<<endl;
return 0;
}