编写一个程序，对输入的任意正整数n，打印出集合{0，1，…，n-1}的所有子集。

一.题目

编写一个程序，对输入的任意正整数n，打印出集合{0，1，…，n-1}的所有子集。

二.示例

//示例一
输入：3
输出：{}，{0}，{1}，{0，1}，{2}，{0，2}，{1，2}，{0，1，2}
//示例二
输入：2
输出：{}，{0}，{1}，{0，1}
1
2
3
4
5
6

三.算法思路

A：根据输入n求出子集的个数即2^n个子集

B：数组的每个元素可以有两种状态：在子数组中和不在子数组中，所有状态的组合就是所有子数组了。

例如：
输入为3，则子集合总数为2^3=8个，集合为{0，1，2}
（说明：3位的二进制数是足够表示小于或等于2^3的十进制数的，拓展即为：n位的二进制数是足够表示小于或等于2^n的十进制数的）
8中状态分别为1~8对应的二进制（0，1的值代表原集合中对应位置上的元素是否在子集合中）
000---->{ ， ，}---->{}
001---->{ ， ，2}---->{2}
010---->{ ，1，}---->{1}
011---->{ ，1，2}---->{1，2}
100---->{0， ，}---->{0}
101---->{0， 2}---->{0，2}
110---->{0，1，}---->{0，1}
111---->{0，1，2}---->{0，1，2}
1
2
3
4
5
6
7
8
9
10
11
12

四.思考流程

1.正常流程

先解决：十进制转二进制

//方法一（用数组存）
int B[32];//数组B用来逆序存放二进制数
int n；//n为十进制数
int i=0;
while (n != 0)
    {
        B[i] = n % 2;
        i++;    //注意这里i多加了一次
        n /= 2;
    }


//方法二（）用数值存
int n，sum；//n为十进制数，sum为n的二进制形式，且为最小位数
int y, x = 1; // y表示余数，x为叠加的系数
while (n != 0)
    {
        y = n % 2;
        sum += x * y;
        x *= 10;
        n /= 2;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

再解决：根据二进制1的位置输出集合中相应位置的元素

int m;//m表示集合的元素个数

for(int i=0;i<m;i++)
{
   if(B[i]=1)
   printf(i);
}
1
2
3
4
5
6
7

准备以上两点即可解决本问题，格式方面简单处理一下

#include 
#include
int main(){
	int n;
	printf("请输入n的值："); 
    scanf("%d",&n); 
    int m=pow(2,n);
    for(int i=0;i<m;i++)
    {
	    int B[32];	//32可以换成n 
	    int t=0;
	    int tmp=i;
	    //转二进制 
		while (tmp != 0)
	    {
	        B[t] = tmp % 2;
	        t++;   
	        tmp/= 2;
	    }
	    //输出 
	    printf("{");
	    int flag=0; //flag用来控制逗号的输出 
	    for(int j=0;j<n;j++)
		{
		   if(B[j]==1)
		   {
		   	if(flag==0)
			 {
			   	printf("%d",j);
			   	flag=1;
			 }
			else
			{
				printf(",%d",j);
			} 
		   }
		}
        printf("}");
	    printf("\n");
    }
	return 0;
}

运行结果：
请输入n的值：3
{}
{0}
{1}
{0,1}
{2}
{0,2}
{1,2}
{0,1,2}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

2.精简流程

a.刚才的流程是分为两个步骤，先转二进制，再根据二进制1的位置输出集合中相应位置的元素

b.现在思考这两个步骤是否可以化简，显然是可以的，因为在转二进制的同时会出现对应的值和位置，足够判断集合中的对应位置的元素是否应该出现在该轮的子集合中

#include 
#include
int main(){
	int n;
	printf("请输入n的值："); 
    scanf("%d",&n); 
    int m=pow(2,n);
    for(int i=0;i<m;i++)
    {
	    int tmp=i;
	    int t=0; //t用来控制二进制与集合对应位置上的元素 
	    //转二进制 并输出 
	    int flag=0; //flag用来控制逗号的输出 
	    printf("{");
		while (tmp != 0)
	    {
	    	if(tmp % 2) 
	    	{
	    		if(flag==0)
				 {
				   	printf("%d",t);
				   	flag=1;
				 }
				else
				{
					printf(",%d",t);
				}
	    	}
	        tmp/= 2;
	        t++;
	    }
	    printf("}");
	    printf("\n");
    }
	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
27
28
29
30
31
32
33
34
35
36

3.标答流程

此过程和精简流程思路一致，但有两点不同

a.判断二进制中1的方法不同 可供参考：二进制中1的个数 - 力扣（LeetCode）

for(int j=0;j<n;++j)
{
	if(i&(1<<j))
	printf("i转化为二进制的逆向第j位的值为1")；
}
1
2
3
4
5

解释：

b.没有将单个子集合拆开输出，而是先将单个子集合存放之数组，一轮循环完成后再输出

#include 
#include
int main(){
	int n;
	printf("请输入n的值："); 
    scanf("%d",&n); 
    int m=pow(2,n);//m为集合的子集合的个数 
    int subsets[n];//存放单个子集合中的元素 
    for(int i=0;i<m;i++)
    {
	    int nums=0; //自己中元素的格式，后面会动态增加
	    for(int j=0;j<n;++j)
	    {
	    	int tmp; //用于检查第j位的元素是否存在于该子集中，可以去掉，结果无影响，答案带着没办法，它可能是想将if语句中的1<
	    	tmp=1<<j;
	    	if(i&(1<<j))
	    	  subsets[nums++]=j;
	    }
	    //输出子集内容
	    printf("{");
		for(int j=0;j<nums;++j)
		{
			printf("%d",subsets[j]);
			if(j<nums-1)
			printf(",");
		} 
	    printf("}");
	    printf("\n");
    }
	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
27
28
29
30
31

五.总结

二进制中1的个数 - 二进制中1的个数 - 力扣（LeetCode）

位运算的重要性