AcWing 1572. 递归实现指数型枚举 II
原题链接
简单
作者:
orange0912
,
2021-01-04 16:06:25
,
所有人可见
,
阅读 1039
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=30;
int d[N];//存储原始数据,后续需排序好
bool st[N];//存储每次选择时是否选中
int n;
//枚举到第u下标开始的一段数,前u-1段已经完成好
void dfs(int u )
{
if(u==n)//已经枚举到最后一段结束了
{
for(int j=0;j<n;j++)
if( st[j]==true) printf("%d ",d[j]); //选中的数进行打印
puts("");
return;
}
// 0 1 2 3 4 5
// 1 1 1 1 2 2
// u k
int k=u;
while(k<n&&d[k]==d[u]) k++;//找到下一次不一样的数的开始位置
//下一轮要递归的 种数 就是k下标的那个数
//每种数 一共有k-u个,可以选择0,1,2...k-u个,j代表选择个数
dfs(k);//先处理选择0个的情况,此时st数组都依然是false
for(int j=u;j<k;j++) //
{
st[j]=true;//一个个选中
dfs(k);
}
//u---k-1这段数一个个考察完毕后要统一恢复现场
for(int j=u;j<k;j++)
st[j]=false;
}
int main( ) {
cin>>n;
for(int i=0;i<n;i++)
cin>>d[i];
sort(d,d+n);
dfs(0);//从0下标开始深搜
return 0;
}