题目链接

题目大意

从1~n这n个整数中随机选出m个,输出所有的选择方案。n>0,0<=m<=n,n+(n-m)<=25

解题思路

递归的机制

采用”堆栈结构”实现函数调用,在汇编语言中,把函数所需的第k个,第k-1个,…,第一个参数依次入栈,然后执行 call 指令。当前语句的下一条语句的地址入栈,然后跳转到 idx 位置的语句。在函数返回时执行 ret 指令,把返回地址出栈,并跳转到该地址继续执行。
函数定义中C++局部变量,在每次执行 call 与 ret 指令时,也会在”栈”中相应的保存与复原,而作用范围超过该函数的变量,以及通过 new 与 malloc 函数动态分配的空间则保存在另外一块称为”堆”的结构中。栈指针、返回值、局部的运算会借助CPU的”寄存器完成”

1.局部变量在每层递归中占有一份空间,声明过多或递归过深就会栈溢出。

2.非局部变量对于各层递归都共享同一份空间,需要及时维护,还原现场,以防止在各层递归之间存储和读取的数据互相影响。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int>v,ans[N];
int st[N],top=0,idx=0,n,m;
void call(int x,int ret_addr) //模拟计算机汇编指令call
{
    int old_top=top;
    st[++top]=x;  //参数x
    st[++top]=ret_addr;   //返回地址标号
    st[++top]=old_top;  //在栈顶记录以前的top值
}
int ret()  //模拟计算机汇编指令ret
{
    int ret_addr=st[top-1];
    top=st[top];  //恢复以前的top值
    return ret_addr;
}
int main()
{
    scanf("%d%d",&n,&m);
    int id=0;
    call(1,0); //call(1)
    while(top){
        int x=st[top-2];  //获取参数
        switch(idx){
            case 0:
                if(v.size()>m||v.size()+(n-x+1)<m){
                    idx=ret();  //return
                    continue;
                }
                if(x==n+1){
                    for(int i=0;i<v.size();++i)
                        ans[id].push_back(v[i]);
                        id++;
                        idx=ret();   //return
                        continue;
                }
                call(x+1,1);  //相当于calc(x+1),返回后会从case 1继续
                idx=0;
                continue;  //回到while循环开头,相当于开始新的递归
            case 1:
                    v.push_back(x); //相当于calc(x+1),返回后会从case 2继续
                    call(x+1,2);
                    idx=0;
                    continue;  //回到while循环开头,相当于开始新的递归
            case 2:
                    v.pop_back();
                    idx=ret();   //相当于calc函数的结尾,执行return
        }
    }
    for(int i=id-1;i>=0;--i){
        for(vector<int>::iterator it=ans[i].begin();it!=ans[i].end();++it){
            cout<<*it<<" ";
        }
        puts("");
    }
    return 0;
}

一个爱折腾且喜欢研究算法的大学生