题目描述

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式
两个整数 n,m ,在同一行用空格隔开。

输出格式
按照从小到大的顺序输出所有方案，每行1个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。

数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25

样例

输入样例：
5 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 
思考题：如果要求使用非递归方法，该怎么做呢？

算法1

大佬们都在炫技，我就写一个简单点的吧
十分十分朴素的做法，维护一个长度m + 1的数组（1~m, 0号位空着)
从1 2 3 … m 列举到 n-m+1 n-m+2 … n

思路也很简单，如果第m位小于n，则第m位+1就是下个组合。
例如 1 2 3 -> 1 2 4 -> 1 2 5
如果第m位等于n，就向前搜索可以+1 的位置，也就是小于上限: n - (m - pos)
然后该位置+1，从pos到m，重新初始化，f[pos+1] = f[pos]+1;
例如：
1 2 5 -> 1 3 4
1 4 5 -> 2 3 4
如果向前搜索到pos = 0,说明已经列举完了，break

采用的算是模拟的方法，时间复杂度比起递归还是慢了些，因为要向前搜索，还要向后赋值

C++ 代码

#include <iostream>
using namespace std;

int n, m; 
int f[1010];

int main()
{
    cin >> n >> m;
    if(!n||!m)  return 0;
    for(int i = 1; i <= m; ++i)
        f[i] = i;

    do{
        for(int i = 1; i <= m; ++i)
            cout<<f[i]<<' ';
        cout<<endl;

        if(f[m] < n)
            ++f[m];
        else
        {
            int pos = m - 1;
            while(f[pos] == n + pos - m)    //找到可以 ++ 的位置
                --pos;
            if(!pos)    break;  //如果是0说明找完了
            ++f[pos++];
            while(pos <= m)
                f[pos] = f[pos-1] + 1, ++pos;   //更新值
            --pos;
        }

    }while(1);
    return 0;
}