组合数

题目 递归实现组合型枚举

image-39c4085b

思路分析

和排列问题差不多 枚举每个位置应该是几

但组合不在乎顺序 所以得减去一些没必要的枝

比如123 132 213 231 321 321只需要保留123

所以判断后一个数大于前一位置的数时 停止此轮（不满足递增 剪枝）

image-21183b17

可以发现还能够剪枝

比如第一位放4 5的情况可以直接不做

因为4后面可枚举的数加起来也不够3位 所以直接可以剪掉

u-1+n-start+1=u+n-start<m

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=30;

int way[N];

int n,m;

void dfs(int u,int start){

    if(u+n-start<m)//剪枝

        return;

    if(u==m+1){

        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;

    }

}

int main()

{

    cin>>n>>m;

    dfs(1,1);//3个参数 每个位置是几的way数组 当前位置u 当前可枚举最小数值

    return 0;

}

同类题型

视频讲解

⬅️ 组合型（n中选m 不考虑顺序） 🏠 00-刷题理模型 ➡️ 选数