c++ 从1到n的整数中(1,2,……,n)取出r个整数(a1,a2,……,ar ),其中a1<a2<……,<ar ,编程打印出全部满足上述关系的a1,a2,……,ar 的组合。
时间: 2023-05-26 11:01:48 浏览: 113
c++输入一个整数,输出一个整数
可以使用回溯算法求解。具体步骤如下:
1. 定义一个数组res用于保存满足条件的组合。
2. 编写递归函数helper(start, n, r, combo),其中:
- start表示当前需要选择的数字的起始位置。
- n表示整数范围(1~n)。
- r表示需要选择的数字个数。
- combo表示当前已选出的数字组合。
在递归函数中,需要进行以下操作:
- 如果combo中已经有r个数字了,说明已经选择了需要的数字,将当前组合添加到res中,并返回。
- 否则,从start到n中选择一个数字i加入组合,然后递归调用helper(i+1, n, r, combo+[i])向后查找。
3. 调用递归函数helper(1, n, r, [])开始查找所有满足条件的组合。
4. 最后返回res。
代码示例:
```
def combinations(n: int, r: int) -> List[List[int]]:
"""
从1到n的整数中(1,2,……,n)取出r个整数(a1,a2,……,ar ),
其中a1<a2<……,<ar ,打印出全部满足上述关系的a1,a2,……,ar
的组合。
"""
res = []
def helper(start, n, r, combo):
if len(combo) == r:
res.append(combo)
return
for i in range(start, n+1):
helper(i+1, n, r, combo+[i])
helper(1, n, r, [])
return res
```
阅读全文