#9951. 组合的输出

组合的输出

组合的输出


任务总览

任务名称 时间限制 内存限制 分数
组合的输出 1 秒 256 MiB 100

题目描述

排列与组合 是常见的数学方法。组合指的是从 n 个元素中 ​选取 ​r 个元素​,且 ​不考虑顺序​。

我们可以简单地将 n 个元素理解为 ​**自然数 1,2,…,n**​,从中选取 r 个数。


输入格式

  • 一行​,包含两个 自然数nr1 < n < 210 ≤ r ≤ n)。

输出格式

  • 所有的组合​,每一行输出一个组合,元素按 从小到大的顺序 排列。
  • 每个元素占 3 个字符宽度​(即 setw(3) 格式)。
  • 所有组合按字典序排列​。

样例

输入

5 3

输出

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

题目分析

  1. 组合问题的特点
    • 组合和排列的 不同 之处在于:​组合不考虑顺序​,即 {1,2,3}{3,2,1} 视为 ​相同的组合​。
    • 递归回溯生成 ​所有的组合​,​保证字典序​。
  2. 求解思路(递归 + 回溯)
    • 使用回溯法​,每次从 1n选择一个数字​,然后递归选择 ​下一个更大的数字​,直到选择了 r 个数。
    • 格式化输出​,每个数字 ​占 1 格字符宽度​。

时间复杂度分析

组合数的数量 由公式 C(n, r) = n! / (r!(n-r)!) 计算。 由于 1 < n < 21,最大情况下 C(20, 10) = 184756,​计算量可接受​。


结论

  • 采用 递归 + 回溯 方法求解。
  • 确保按字典序输出​。
  • 格式化输出​(setw(1))。