回溯法 有n个数,输出其中r(r<=n)个数的所有组合代码
时间: 2023-11-27 14:49:11 浏览: 29
以下是使用回溯法实现输出n个数中r个数的所有组合的代码:
```python
def combinations(n, r):
res = []
def backtrack(start, path):
if len(path) == r:
res.append(path[:])
return
for i in range(start, n+1):
path.append(i)
backtrack(i+1, path)
path.pop()
backtrack(1, [])
return res
```
其中,`backtrack`函数采用回溯法实现。`start`表示枚举数的起始位置,`path`表示当前已经选取的数。当`path`中的元素个数等于`r`时,将`path`加入结果集`res`中。接着,从起始位置`start`开始枚举,每次选取一个数并将其加入`path`中,再递归调用`backtrack`函数,继续从下一个位置开始选取数。当递归返回时,将`path`中的最后一个数弹出,回溯到上一层递归调用的状态。
最后,调用`combinations`函数即可得到n个数中r个数的所有组合。
相关问题
回溯法 有n个数,输出其中r(r<=n)个数的所有组合代码使用c语言
以下使用递归实现回溯法求解组合的C语言代码:
```c
#include <stdio.h>
void combination(int arr[], int start, int n, int r, int result[], int res_idx) {
if (res_idx == r) { // 组合中已选r个数,输出结果
for (int i = 0; i < r; i++) {
printf("%d ", result[i]);
}
printf("\n");
return;
}
for (int i = start; i < n; i++) {
result[res_idx] = arr[i];
combination(arr, i + 1, n, r, result, res_idx + 1); // 递归求解下一位
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int r = 3;
int result[r];
combination(arr, 0, n, r, result, 0); // 从第一个数开始求解组合
return 0;
}
```
在这个程序中,`combination`函数接收一个数组 `arr`,一个起始位置 `start`,数组长度 `n`,组合中需要选的数的个数 `r`,一个用于存储结果的数组 `result`,以及一个当前结果数组已选的数的个数 `res_idx`。函数的作用是从数组中选取 `r` 个数,输出所有可能的组合。
函数的实现中,当 `res_idx` 等于 `r` 时,已经选出了 `r` 个数,输出结果。否则,从当前位置开始,循环遍历数组中剩余的数,将当前数加入结果数组中,并递归调用 `combination` 函数求解下一位。递归结束后,将当前数从结果数组中移除,继续循环遍历数组中的下一个数。
用C++编程,有n个数,输出其中r(r<=n)个数的所有组合。
可以使用回溯法(backtracking)来解决这个问题,以下是一份C++实现代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<vector<int>>& res, vector<int>& path, int n, int r, int start) {
if (path.size() == r) {
res.push_back(path);
return;
}
for (int i = start; i <= n; i++) {
path.push_back(i);
backtrack(res, path, n, r, i + 1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int r) {
vector<vector<int>> res;
vector<int> path;
backtrack(res, path, n, r, 1);
return res;
}
int main() {
int n = 5, r = 3;
vector<vector<int>> res = combine(n, r);
for (auto& v : res) {
for (auto& num : v) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
```
其中,backtrack函数用于递归搜索所有的组合,res用于存储所有的组合,path用于存储当前的组合,n表示一共有n个数,r表示需要选出r个数,start表示搜索的起点。
在backtrack函数中,首先判断当前已经选择的元素个数是否等于r,如果是,则将当前组合加入res中;否则,从start开始遍历所有可选的元素,并将其加入path中,继续递归调用backtrack函数,直到选择的元素个数等于r或者已经选择了n个元素。
在main函数中,调用combine函数获取所有的组合,并输出结果。