题目描述

排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r < ＝ n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。现要求你不用递归的方法输出所有组合。
例如n ＝ 5 ，r ＝ 3 ，所有组合为：
1 2 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 5 

输入

一行两个自然数n、r ( 1 < n < 21，1 < ＝ r < ＝ n )。

输出

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

题目链接：Problem B: 【递归入门】组合的输出 - Codeup新家

分析：这道题算是题目A生成全排列的进阶版，要求一行中的排列元素按照从小到大顺序，也就是部分排列不符合要求。如果使用递归，只需要在生成排列的时候添加限制条件即可，也就是当前index位置放的数字，不能小于index。比如，第2个位置上不能出现数字1，第3个位置不能出现数字1,2······

但是题目要求不能使用递归。可以用循环模拟递归，每次循环时填入一个数字，当填了r个数字时，输出这个排列，并弹出最后一个数字。如果还有能用的数字，则继续填，否则再弹出当前的最后一个数字。直到得到所有的排列，退出循环。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define ll long long
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,a) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<endl
using namespace std;int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);clock_t start=clock();#endif //testint n,r;while(~scanf("%d%d",&n,&r)){vector<int>vec;int flag[n+5]={0};while(1){if(vec.size()==r){for(int i=0;i<r;++i)i==0?printf("%d",vec[i]):printf(" %d",vec[i]);printf("\n");vec.pop_back();if(r==1&&vec[0]==n)break;}else{int f=0;for(int i=1;i<=n;++i){if(!flag[i]){vec.push_back(i);f=1;flag[i]=1;break;}}if(!f){int cnt=vec.size();for(int i=vec[cnt-1];i<=n;++i)flag[i]=0;for(int i=0;i<cnt;++i)flag[vec[i]]=1;vec.pop_back();}}if(vec[0]>n-r+1)break;}}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位#endif //testreturn 0;
}