labuladong讲解

你好，同学。欢迎来到 NOI 系列专题讲座。上一节课我们学习了“子集”问题（即 $2^n$ 的搜索空间），今天我们进阶到组合数学中另一个极其重要的模型——组合 (Combinations)，即在 $n$ 个元素中选出特定的 $k$ 个元素。

一、 题目描述 (NOI 风格)

题目名称：组合 (Combinations) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定两个整数 $n$ 和 $k$，请找出所有范围在 $[1, n]$ 范围内、包含 $k$ 个数字的所有可能组合。 注意：

1. 组合内数字的顺序不作要求（即 $\{1, 2\}$ 和 $\{2, 1\}$ 视为同一个组合）。
2. 你可以按任意顺序输出这些组合。

【输入格式】 输入仅一行，包含两个整数 $n$ 和 $k$，以空格隔开。

【输出格式】 输出若干行，每行包含 $k$ 个正整数，表示一个符合条件的组合。数字之间用空格隔开。

【样例输入】

4 2

【样例输出】

1 2
1 3
1 4
2 3
2 4
3 4

【数据范围】 对于 $100\%$ 的数据：$1 \le n \le 20$，$1 \le k \le n$。

二、 预备知识点

1. 限定深度的回溯法 (Backtracking)：在搜索树中，我们只需要达到深度为 $k$ 的节点。
2. 搜索剪枝 (Pruning)：这是 NOI 竞赛提分的关键。如果当前剩余的候选数字个数不足以填满剩下的 $k$ 个位置，则直接停止搜索。
3. 组合数计算：总方案数为 $C_n^k = \frac{n!}{k!(n-k)!}$。

三、 启发式思路引导：草稿纸上的推理

我们要从 $1, 2, 3, 4$ 选出 $k=2$ 个数。请在草稿纸上模拟这个“选择”的过程：

1. 防止重复的技巧：顺序性

为了不选出重复的组合（例如避免选了 {1, 2} 又选 {2, 1}），我们在搜索时要规定：下一个选的数必须比上一个选的数大。

2. 搜索树绘制

• 第一层决策（选第 1 个数）：
  • 选 1 $\rightarrow$ 接下来从 {2, 3, 4} 里选 1 个。
  • 选 2 $\rightarrow$ 接下来从 {3, 4} 里选 1 个。
  • 选 3 $\rightarrow$ 接下来从 {4} 里选 1 个。
  • 选 4 $\rightarrow$ 接下来没得选了（因为要选 2 个，选了 4 后面就空了）。

3. 剪枝优化（核心逻辑）

观察上面的“选 4”分支。如果我们现在还需要选 need 个数，而后面只剩下 rest 个数，如果 rest < need，这个分支就是死路一条，不需要再递归下去了。

四、 复杂度分析与时间优化建议

• 时间复杂度：

  • 最坏情况下，搜索规模由组合数 $C_n^k$ 决定。
  • 加上输出的时间，总复杂度约为 $O(k \cdot C_n^k)$。
  • 优化建议：在 $n=20$ 时，$C_{20}^{10} = 184,756$，这个规模很小。但在 NOI 赛场上，若 $n$ 达到 40 或更高，必须使用剪枝逻辑：for (int i = start; i <= n - (k - path.size()) + 1; ++i)。

• 空间复杂度：

  • 递归深度为 $O(k)$。
  • 存储单个组合的路径空间为 $O(k)$。

五、 算法流程图 (C++14 风格伪代码)

我们使用带剪枝的回溯法来描述：

graph TD
    Start(开始) --> Init(初始化 path 数组)
    Init --> CallDFS("DFS(起始数字 1)")

    subgraph DFS_Process [递归函数 DFS-start]
    Check{path.size == k ?}
    Check -- Yes --> Output("输出 path 并返回")
    Check -- No --> LoopInit("计算当前还需要选 need = k - path.size 个数")
    LoopInit --> LoopStart("循环 i 从 start 到 n")
    
    LoopStart --> Pruning{"剩余数字够吗? i <= n - need + 1"}
    Pruning -- No --> Return((回溯返回))
    Pruning -- Yes --> Action("path.push_back(i)")
    
    Action --> Recur("DFS(i + 1)")
    Recur --> Pop("path.pop_back 恢复现场")
    Pop --> NextI("i++ 继续循环")
    NextI --> LoopStart
    end

    Output --> End(结束)

六、 读题关键词总结

在 NOI 竞赛中处理“组合类”搜索题，请重点关注以下词汇：

1. “$n$ 个数中选 $k$ 个”：明确告诉你要控制搜索深度。
2. “范围在 $[1, n]$”：确定了搜索范围的边界。
3. “不计顺序” (Combination)：这是在提醒你，搜索时要维持一个 start_index 参数，确保序列是递增的，从而实现天然去重。
4. “所有可能”：意味着需要遍历整个解空间，注意控制好回溯时的状态重置（pop_back）。

教练点评： “组合”是搜索算法的入门基石。掌握了“基于 start 位置的递增搜索”和“基于剩余容量的剪枝”，你就掌握了处理组合问题的精髓。相比于“子集”问题，它多了一个“深度限制”，这让剪枝变得更加高效。去试着实现它吧！