洛谷P1157组合的输出

与排列差不多但是又差的多，详情看题：

题目描述

排列与组合是常用的数学方法，其中组合就是从nn个元素中抽出rr个元素(不分顺序且r \le n)r≤n)，我们可以简单地将nn个元素理解为自然数1,2,…,n1,2,…,n，从中任取rr个数。

现要求你输出所有组合。

例如n=5,r=3n=5,r=3，所有组合为：

12 3 , 1 2 4 , 1 2 5 , 1 3 4 ,1 3 5 , 1 4 5 , 2 3 4 , 2 3 5 , 2 4 5 , 3 4 5123,124,125,134,135,145,234,235,245,345

输入格式

一行两个自然数n,r(1<n<21,0 \le r \le n)n,r(1<n<21,0≤r≤n)。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

分为两个办法

首先用比较熟悉的STL，方法如下：

#include<bits/stdc++.h>using namespace std;int n,r;int a[25];int main(){    cin>>n>>r;    for(int i=r+1;i<=n;i++)//因为是从1~5进行组合排列     {        a[i]=1;//用1来表示不选     }    do    {        for(int i=1;i<=n;i++)        {            if(a[i]==0)//用0来表示选中了             {                printf("%3d",i);            }        }        cout<<endl;    }while(next_permutation(a+1,a+n+1));//同理     return 0;}

另外一种就是暴力搜索的递归——dfs，虽然我不喜欢用但是这种方法具有普遍性；

附上代码：

#include<bits/stdc++.h>using namespace std;int n,k;int a[25];void dfs(int step)//step表示到了那一层 {    if(step==k+1)    {        for(int i=1;i<=k;i++)        {            printf("%3d",a[i]);        }        printf("\n");          }     for(int i=a[step-1]+1;i<=n;i++)//只要从a[step]大 即a[step]+1就行      {         a[step]=i;//存值          dfs(step+1);//进入下一层       } }int main(){    cin>>n>>k;    dfs(1);//照应step-1        return 0;}

并且推荐一下讲的很好的讲解视频：https://www.bilibili.com/video/BV1JK41137b9?from=search&seid=3290462022916294689&spm_id_from=333.337.0.0

就这样吧。