93. 递归实现组合型枚举

题目链接

从 1∼n 这 n 个整数中随机选出 m 个，按照从小到大的顺序输出所有方案。

枚举每个位置上可以选哪些数固定枚举顺序（从小到大）

u 表示当前枚举到第几个位置上的数需要剪枝（当u>1时，当前数需要比前一个数大）

O ( n ! ) O(n!) O(n!)

数组 st 记录选和不选的状态数组 num 记录选择的序列暴力枚举每一个数是否符合条件是否可选

#include
#define endl 'n' 
#define int long long
using namespace std;
const int N = 2e5+10;
typedef long long ll;
int n,m;
int num[50];
int st[50];
// 枚举每个位置上可以选哪些数，保证升序
void dfs(int u)
{
    if(u>m)
    {
        for(int i=1;i<=m;i++)
        {
            cout<num[u-1])
                {
                    num[u]=i;
                    st[i]=1;
                    dfs(u+1);
                    st[i]=0;
                }
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    dfs(1);
    return 0;
}

O ( n ! ) O(n!) O(n!)

数组 st 记录选和不选的状态数组 num 记录选择的序列由于当前数比前一个数大，则枚举起点可以为 num[u-1]+1

#include
#define endl 'n' 
#define int long long
using namespace std;
const int N = 2e5+10;
typedef long long ll;
int n,m;
int num[50];
int st[50];
// 枚举每个位置上可以选哪些数，保证升序
void dfs(int u)
{
    if(u>m)
    {
        for(int i=1;i<=m;i++)
        {
            cout<>n>>m;
    dfs(1);
    return 0;
}

指数型枚举变形，剪纸思路