第16课:子集枚举

潘CSP100班

2024-07-19 9:59:44
2024-08-18 12:54:00

信息与公告

1、子集枚举问题:求n个元素的所有子集。
例如:{1, 2, 3}的所有子集共8个:{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

2、子集枚举代码框架
例如,枚举从n个元素中选任意个元素的所有方案(共2^n种)

for (int i = 0; i < (1<<n); i++)      // i从0枚举到2^n -1,这里(1<<n)表示2^n。
{                    //(如果不输出空集,则i从1开始)        
	bitset<30> b(i);   // 将i转换为二进制数b,即0…0到1…1 
	for (int j=0; j<n; j++)    // 找出b中所有的1,表示a中对应元素被选入
	{
		if (b[j]==1)  // b的第j位为1,表示a的第j个元素被选入
		{
			……
		}
	}
}