枚举子集¶
枚举定长子集¶
增量构造法¶
原问题：\(1,2,3...n\) 这 \(n\) 个数中选 \(m\) 个
如果选择 1 ，则原问题变为：\(2,3,...n\) 这 \(n-1\) 个数中选 \(m-1\) 个
所以原问题可以递归求解，代码如下：
void subset(int a[],int l,const int & r,const int & int n,int m){
// l,r 为枚举区间
if(m==0){
// Finished!
return;
}
for(int i=l;i<=r;i++){
// Select a[i]
subset(a,l+1,r,n,m-1);
}
}
注意维护每次调用的入口环境：如果要维护所选择元素的 sum ，应该这样写
void subset(int a[],int l,const int & r,const int & int n,int m,int sum){
if(m==0){
cout<<sum<<' ';
return;
}
for(int i=l;i<=r;i++)
// sum+=a[i]; 入口环境破坏
subset(a,l+1,r,n,m-1,sum+a[i]);
}
可以看到，递归方法传入参数很多，效率不高
位向量法¶
用 0 表示 “不选”，1 表示 “选”，则可以将原问题转化为 0-1 序列的全排列问题
手动构造初始 0-1 排列（ 最大 排列 ）后，再调用 STL 里的 prev_permutation 即可
如：从 6 个元素中选出 3 个，则最大的 0-1 序列为
\[1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\]
可用 prev_permutation 函数，详见 枚举排列
代码如下：
// Input: n, m, a[n];
bool* flag=new bool[n](); // 初始化为 0
for(int i=0;i<m;i++)
flag[i]=true; // 构造初始排列
while(prev_permutation(flag,flag+n)){
// do something
}
枚举不定长子集¶
增量构造法¶
void subset(int d[],int a[],int l,int r){
for(int i=0;i<l;i++)
cout<<d[a[i]];
if(l) cout<<endl;
// 放入第 l 个元素
for(int i=l?a[l-1]+1:0;i<=r;i++){
// l?a[l-1]+1:0 确定从哪里开始放
// 以 d[]={1,2,3}，a[]={0,1} 为例：
// 放第三个元素时，要从下标为 a[2-1]+1=2 的开始放
a[l]=i;
subset(d,a,l+1,r);
}
}
解答树结点 \(2^n\) ，刚好是所有可能的组合数，不能再少，但递归算法天生较慢，可能爆栈
位向量法¶
void subset(int d[],bool a[],int l,int r){
// [l,r] 枚举区间 e.g. a[10] => [0,9]
if(l>r){
for(int i=0;i<=r;i++)
if(a[i]) cout<<d[i]<<' ';
cout<<endl;
return;
}
a[l]=0;
subset(d,a,l+1,r);
a[l]=1;
subset(d,a,l+1,r);
}
位向量法易懂、好写，但略慢（ 解答树结点 \(2^{n+1}-1\) 略多 ）
二进制法¶
void subset(int d[],int siz){
// 枚举所有子集对应的二进制编码 0,1,2,...,1<<siz
for(int i=0;i<(1<<siz);i++){
print_subset(d,siz,i);
}
}
void print_subset(int d[],int siz,int code){
// 打印编码为 code 的子集
for(int i=0;i<siz;i++){
if(code&(1<<i)) cout<<d[i]<<' ';
// 第 i 位为 1 ，输出 d[i]
}
cout<<endl;
}