AcWing 93. 递归实现组合型枚举

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=30;  // 多开几个，防止边界越界
int n,m;
int way[N];  // 表示方案

// u 代表当前枚举的位置，start表示从第几个数开始枚举
void dfs(int u,int start){
  // 剪枝(优化步骤)
  if(u-1+ n-start+1<m){ // 如果把后面所有数都选上，都不够m个，当前分支就一定无解
    return ;
  }
  
  
  if(u > m){
      for(int i=1;i<=m;i++){
        cout<<way[i]<<" ";   // 输出方案 
      }
    cout<<endl;
    return;
  }
  for(int i=start;i<=n;i++){
    way[u]=i;
    dfs(u+1,i+1);
    // 恢复现场
    way[u]=0; // 0表示为空
  }
}


int main(){
  cin>>n>>m;
  dfs(1,1);
  return 0;
}