本课时有配套视频讲解，购买后即可观看（永久有效）
组合问题汇总
一、课上练习
编程练习
- 组合枚举：L3541
二、知识总结
✨ 相同元素分配问题
将 n 个相同的元素分配给 m 个不同的容器，允许有空容器，使用隔板法的变形。方案数为 C(n+m-1, m-1)。如果要求每个容器至少分到一个元素，则方案数为 C(n-1, m-1)。
✨ 相同元素选择问题
从若干种相同的物品中选取指定数量的物品，本质上是求不定方程的非负整数解的个数。利用隔板法，等价于相同元素分配问题。
✨ 平均分组问题
将 n 个不同元素平均分成 k 组（每组 n/k 个），需要注意分组是否有标号：
- 有标号分组（分给不同的人）：
C(n, n/k) × C(n-n/k, n/k) × ... × C(n/k, n/k) - 无标号分组（仅分组）：在有标号分组的基础上除以
k!，因为组与组之间无序
✨ 不同元素分类问题
将 n 个不同元素按照某种属性分成若干类，每一类的方案独立计算后相加，本质上是加法原理的应用。
✨ 不同元素分步问题
将 n 个不同元素通过多个步骤进行分配或选择，每一步的方案数相乘，本质上是乘法原理的应用。通常结合组合数逐步计算每一步的选择方案。
✨ 执行示例
以具体例题追踪各类组合问题的解法：
隔板法示例： 把 10 个相同的苹果分给 3 个小朋友，每人至少 1 个，有多少种分法？
将 10 个苹果排成一排：🍎🍎🍎🍎🍎🍎🍎🍎🍎🍎
在 9 个间隔中选 2 个放隔板：
C(9, 2) = 9! / (2! × 7!) = 36 种
例如：🍎🍎🍎 | 🍎🍎🍎🍎 | 🍎🍎🍎 表示分配 (3, 4, 3)允许为空的隔板法： 把 10 个苹果分给 3 个小朋友，允许有人不分到。
思路：先给每人"借" 1 个苹果，变成 13 个苹果每人至少 1 个
C(13-1, 3-1) = C(12, 2) = 66 种
公式：C(n+m-1, m-1) = C(10+3-1, 3-1) = C(12, 2) = 66平均分组示例： 把 6 本不同的书平均分成 3 组，每组 2 本。
有标号分组（分给3个人）：
C(6,2) × C(4,2) × C(2,2) = 15 × 6 × 1 = 90
无标号分组（仅分组）：
90 / 3! = 90 / 6 = 15验证（6 本书 {A,B,C,D,E,F} 分成 3 组，每组 2 本）：
1{AB,CD,EF}, {AB,CE,DF}, {AB,CF,DE},
2{AC,BD,EF}, {AC,BE,DF}, {AC,BF,DE},
3{AD,BC,EF}, {AD,BE,CF}, {AD,BF,CE},
4{AE,BC,DF}, {AE,BD,CF}, {AE,BF,CD},
5{AF,BC,DE}, {AF,BD,CE}, {AF,BE,CD}
6共 15 种✨ 解题步骤详解
组合问题的解题策略选择：
- 相同元素分配，每份至少 1 个 → 隔板法：C(n-1, m-1)
- 相同元素分配，允许空份 → 隔板法变形：C(n+m-1, m-1)
- 不同元素平均分组：
- 分给不同的人：直接用组合数连乘
- 仅分组（无标号）：组合数连乘后除以 k!
- 至少/至多问题 → 考虑间接法：总数 - 不满足条件的数
- 复杂分配 → 分步计算：用乘法原理逐步选择
例题： 12 个相同的球放入 4 个不同的盒子，每个盒子至少 2 个球。
步骤1: 先给每个盒子放 2 个球，还剩 12 - 4×2 = 4 个球
步骤2: 4 个球放入 4 个盒子（允许为空）
步骤3: C(4+4-1, 4-1) = C(7, 3) = 35 种✨ 常见错误
- 混淆"相同元素"和"不同元素"：相同元素的分配只看数量，不同元素的分配要考虑具体是哪些元素
- 隔板法条件不满足：标准隔板法要求每份至少 1 个，如果允许为空需要先做转换
- 平均分组忘记除以 k!：如果组与组之间无标号（不分给具体的人），必须除以组数的阶乘
- 分步分组中组合数更新不及时：每一步选完后，剩余元素数量要相应减少
- "至少"问题直接分类太多：当"至少"的情况很多时，应优先考虑间接法（总数 - 不满足的），而不是逐一列举
- 隔板法与排列混淆：隔板法处理的是相同元素的分配，结果是组合数；如果元素不同，需要额外考虑排列
✨ C++ 代码实现
递归生成组合
从n个数中选m个的所有组合
1#include <iostream>
2using namespace std;
3
4int n, m;
5int chosen[25]; // 存储当前选择的元素
6
7void dfs(int step, int start) {
8 if (step > m) {
9 for (int i = 1; i <= m; i++) {
10 cout << chosen[i] << (i == m ? '\n' : ' ');
11 }
12 return;
13 }
14 // 从 start 开始选，保证组合不重复
15 // 剪枝：剩余元素不够选时提前退出
16 for (int i = start; i <= n - (m - step); i++) {
17 chosen[step] = i;
18 dfs(step + 1, i + 1);
19 }
20}
21
22int main() {
23 cin >> n >> m;
24 dfs(1, 1);
25 return 0;
26}输入 5 3，输出：
11 2 3
21 2 4
31 2 5
41 3 4
51 3 5
61 4 5
72 3 4
82 3 5
92 4 5
103 4 5共 C(5,3) = 10 种。
隔板法实现
相同元素分配方案数
1#include <iostream>
2using namespace std;
3
4// 组合数 C(n, m)
5long long C(int n, int m) {
6 if (m > n - m) m = n - m;
7 long long result = 1;
8 for (int i = 0; i < m; i++) {
9 result = result * (n - i) / (i + 1);
10 }
11 return result;
12}
13
14int main() {
15 int n, m;
16 cout << "将 n 个相同物品分给 m 个人" << endl;
17 cin >> n >> m;
18
19 // 每人至少1个
20 if (n >= m) {
21 cout << "每人至少1个: C(" << n-1 << "," << m-1 << ") = "
22 << C(n - 1, m - 1) << endl;
23 }
24
25 // 允许为空
26 cout << "允许为空: C(" << n+m-1 << "," << m-1 << ") = "
27 << C(n + m - 1, m - 1) << endl;
28
29 return 0;
30}用位运算枚举子集
对于小规模问题（n ≤ 20），可以用二进制枚举所有子集：
二进制枚举所有子集
1#include <iostream>
2using namespace std;
3
4int main() {
5 int n;
6 cin >> n;
7
8 // 枚举 {1, 2, ..., n} 的所有子集
9 for (int mask = 0; mask < (1 << n); mask++) {
10 cout << "{ ";
11 for (int i = 0; i < n; i++) {
12 if (mask & (1 << i)) {
13 cout << i + 1 << " ";
14 }
15 }
16 cout << "}" << endl;
17 }
18 cout << "共 " << (1 << n) << " 个子集" << endl;
19
20 return 0;
21}输入 3，输出所有 2^3 = 8 个子集：
1{ }
2{ 1 }
3{ 2 }
4{ 1 2 }
5{ 3 }
6{ 1 3 }
7{ 2 3 }
8{ 1 2 3 }枚举固定大小的子集
枚举大小为m的所有子集
1#include <iostream>
2using namespace std;
3
4int main() {
5 int n, m;
6 cin >> n >> m;
7
8 for (int mask = 0; mask < (1 << n); mask++) {
9 if (__builtin_popcount(mask) != m) continue;
10 cout << "{ ";
11 for (int i = 0; i < n; i++) {
12 if (mask & (1 << i)) cout << i + 1 << " ";
13 }
14 cout << "}" << endl;
15 }
16 return 0;
17}✨ 综合例题
例题1： 从 1~10 中选出 3 个数，使得任意两个数都不相邻，有多少种选法？
分析： 使用插空法思想。先从 10 个位置中去掉被选数之间必须留出的间隔。
选出 3 个数，它们之间要有间隔，相当于：
先"预留"2 个间隔位（3个数之间有2个间隙）
剩余位置数 = 10 - 2 = 8 个位置中选 3 个
C(8, 3) = 56 种例题2： 不定方程 x1 + x2 + x3 + x4 = 10 的非负整数解有多少组？
分析： 这就是把 10 个相同球放入 4 个不同盒子（允许为空）的问题。
C(10 + 4 - 1, 4 - 1) = C(13, 3) = 286 组如果要求每个变量至少为 1（正整数解）：
C(10 - 1, 4 - 1) = C(9, 3) = 84 组如果要求 x1 >= 2, x2 >= 1, x3 >= 0, x4 >= 3 呢？
令 y1 = x1-2, y2 = x2-1, y3 = x3, y4 = x4-3
则 y1 + y2 + y3 + y4 = 10 - 2 - 1 - 0 - 3 = 4（非负整数解）
C(4 + 4 - 1, 4 - 1) = C(7, 3) = 35 组✨ 排列组合问题速查表
| 问题类型 | 方法 | 公式 |
|---|---|---|
| n 选 m 排列 | 排列公式 | A(n,m) = n!/(n-m)! |
| n 选 m 组合 | 组合公式 | C(n,m) = n!/(m!(n-m)!) |
| 相同物分配（每份≥1） | 隔板法 | C(n-1, m-1) |
| 相同物分配（允许空） | 隔板法变形 | C(n+m-1, m-1) |
| 不同物平均分组（无标号） | 组合连乘÷k! | C连乘 / k! |
| 必须相邻 | 捆绑法 | 整体排列 × 内部排列 |
| 互不相邻 | 插空法 | 其余排列 × A(空隙数, 选取数) |
| 有固定顺序 | 定序法 | n! / k! |
| 环排 | 固定一人 | (n-1)! |
| 有重复元素 | 多重排列 | n! / (n1!×n2!×...×nk!) |
| 全错排 | 错排公式 | D(n) = (n-1)(D(n-1)+D(n-2)) |
| 至少/至多 | 间接法 | 总数 - 不满足的 |