组合的输出

任务总览

题目描述

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

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

输入格式

• ​一行​，包含两个 自然数n 和 r（1 < n < 21，0 ≤ 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. 求解思路（递归 + 回溯）
   • ​使用回溯法​，每次从 1 到 n​选择一个数字​，然后递归选择 ​下一个更大的数字​，直到选择了 r 个数。
   • ​格式化输出​，每个数字 ​占 1 格字符宽度​。

时间复杂度分析

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

结论

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