#9951. 组合的输出
组合的输出
组合的输出
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
组合的输出 | 1 秒 | 256 MiB | 100 |
题目描述
排列与组合 是常见的数学方法。组合指的是从 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,2,3}
和{3,2,1}
视为 相同的组合。 - 递归回溯生成 所有的组合,保证字典序。
- 组合和排列的 不同 之处在于:组合不考虑顺序,即
- 求解思路(递归 + 回溯)
- 使用回溯法,每次从
1
到n
选择一个数字,然后递归选择 下一个更大的数字,直到选择了r
个数。 - 格式化输出,每个数字 占 1 格字符宽度。
- 使用回溯法,每次从
时间复杂度分析
组合数的数量 由公式 C(n, r) = n! / (r!(n-r)!)
计算。
由于 1 < n < 21
,最大情况下 C(20, 10) = 184756
,计算量可接受。
结论
- 采用 递归 + 回溯 方法求解。
- 确保按字典序输出。
- 格式化输出(
setw(1)
)。