设计一个递归算法,找出n个自然数(1,2,3,....,n)中取r个数的组合。例如,当n=5,r=3时,所有的组合为: 5 4 3 5 4 2 5 4 1 5 3 2 5 3 1 5 2 1 4 3 2 4 3 1 4 2 1 3 2 1 要求: (1)描述求解该组合问题的递归算法思路; (2)写出算法核心代码,并添加必要的注释。
时间: 2023-05-30 10:05:29 浏览: 130
(1) 递归算法思路:
假设已经求出了从1到n-1中取r个数的所有组合,那么现在考虑从1到n中取r个数的所有组合。可以把问题分解为两个子问题:
1. 从1到n-1中取r个数的所有组合;
2. 从1到n-1中取r-1个数的所有组合,再把n加进去。
最后,将这两个子问题的解合并起来,就可以得到从1到n中取r个数的所有组合。
(2) 算法核心代码:
```
void combination(int n, int r, vector<int>& temp, vector<vector<int>>& result) {
if (r == 0) { // 组合中已经选够了r个数
result.push_back(temp); // 将当前组合加入结果集
return;
}
if (n < r) { // 剩余可选的数不够r个了,直接返回
return;
}
combination(n-1, r, temp, result); // 不选n,从1到n-1中选r个数的组合
temp.push_back(n); // 选n,从1到n-1中选r-1个数的组合,再加入n
combination(n-1, r-1, temp, result);
temp.pop_back(); // 恢复现场
}
```
注释:
- n:表示可选的数的范围是1到n;
- r:表示要选出的数的个数;
- temp:表示当前正在生成的组合;
- result:表示所有生成的组合的集合;
- 当r等于0时,说明已经选够了r个数,将当前组合加入结果集;
- 当n小于r时,说明剩余可选的数不够r个了,直接返回;
- 不选n,从1到n-1中选r个数的组合;
- 选n,从1到n-1中选r-1个数的组合,再加入n;
- 恢复现场,将n从当前组合中删除。