nyoj组合数

时间:2022-06-06 08:01:14

算法:深搜



描述 找出从自然数1、2、... 、n(0<n<10)中任取r(0<r<=n)个数的所有组合。

输入输入n、r。输出按特定顺序输出所有组合。

特定顺序:每一个组合中的值从大到小排列,组合之间按逆字典序排列。样例输入5 3

样例输出543

542

541

532

531

521

432

431

421

321

代码:

 #include<iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
int a[13],b[13],step;
void dfs(int i,int cur,int deep)
{
for(int j=i;j>0;j--)
{
if(!a[j])
{ if(b[cur-1]>j)//控制每位是递减地
{
b[cur]=j;
a[j]=1;
if(cur==deep)
{
for(int k=1;k<=deep;k++)
cout<<b[k];
cout<<endl;
}
dfs(i-1,cur+1,deep);
a[j]=0;
} } }
}
int main()
{
int n,m;
b[0]=12;
while(cin>>n>>m)
{
memset(a,0,sizeof(a));
dfs(n,1,m);
}
return 0;
}