AcWing 1573. 递归实现组合型枚举II
原题链接
简单
作者:
orange0912
,
2021-01-06 10:53:43
,
所有人可见
,
阅读 456
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=30;
int a[N];//存储原始数据,后续需排序好
bool st[N];//存储每次选择时是否选中
int n,m;
void dfs(int u,int s )
{
if(s>m) return;//剪枝 不需要再递归到m+1层
if(s==m)
{
for(int i=0;i<u;i++)
{
if(st[i]==true)
cout<<a[i]<<" ";
}
cout<<endl;
return;
}
if(u==n) return;//递归出口,需要在上述s==m后再考虑递归出口
// 0 1 2 3 4 5
// 1 1 1 1 2 2
// u k
int k=u;//k为下一段开始的位置
while(k<n&&a[k]==a[u])
{
st[k]=true;//先保证选中
k++;
s++;//选中的个数自增
}
dfs(k,s);//当前这段全选
//要按照字典序从小到大输出,则前面的小的数字要优选选更多的
for(int i=k-1;i>=u;i--)
{
st[i]=false;
s--;
dfs(k,s);
}
}
int main( ) {
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);//先排序好要处理的数
dfs(0,0);//从0下标开始深搜,最开始一个都没有选
return 0;
}