排列与组合是常用的数学方法,其中组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r≤n),我们可以简单地将 n 个元素理解为自然数 1,2,…,n,从中任取 r 个数。 现要求你用递归的方法输出所有组合。
时间: 2024-05-02 17:20:50 浏览: 247
以下是Python代码实现:
```python
def combine(n, r):
if r == 0:
return [[]]
elif n < r:
return []
else:
result = combine(n-1, r-1)
for item in result:
item.append(n)
result += combine(n-1, r)
return result
n = 5
r = 3
print(combine(n, r))
```
输出为:
```
[[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]]
```
解释:递归函数 `combine(n, r)` 的作用是返回从 n 个元素中取 r 个元素的所有组合。当 r=0 时,返回空列表的列表,即只有一个空组合。当 n<r 时,返回空列表。否则,递归调用 `combine(n-1, r-1)`,得到从 n-1 个元素中取 r-1 个元素的所有组合,在每个组合的末尾添加 n,再递归调用 `combine(n-1, r)`,得到从 n-1 个元素中取 r 个元素的所有组合,最后将两个列表合并并返回。
阅读全文