算法笔记8.1小节搜索专题-深度优先搜索DFS问题-B-递归入门组合的输出
目录
《算法笔记》8.1小节——搜索专题-＞深度优先搜索（DFS）问题 B: 【递归入门】组合的输出
题目描述
排列与组合是常用的数学方法，其中组合就是从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 )。
输出
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，所有的组合也按字典顺序。
题目链接：
分析：这道题算是题目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 test
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
clock_t start=clock();
#endif //test
int 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 test
clockid_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 //test
return 0;
}