---
title: "组合数"
created: 2025-11-28
tags:
  - 算法
---

# 组合数

## 题目 [**递归实现组合型枚举**](https://www.acwing.com/problem/content/95/)

![[image-39c4085b.png]]

## 思路分析

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

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

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

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

![[image-21183b17.png]]

可以发现还能够剪枝

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

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

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

## 代码实现

```cpp
#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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[简单斐波那契（递归实现）|简单斐波那契（递归实现）]] 🏠 [[00-刷题理模型]] ➡️ [[递归|递归]]