编写程序，采用回溯法输出自然数 1~n 中，任取 r 个数的所有组合。（问 题设定，n=5，r=3）

好的，可以使用递归回溯法来解决这个问题。下面是 Python 实现代码：

def backtrack(combination, start, n, r, result):
    if len(combination) == r:  # 如果组合中的元素个数达到 r，加入结果集
        result.append(combination[:])
        return
    for i in range(start, n+1):  # 从 start 开始，遍历剩余的数
        combination.append(i)
        backtrack(combination, i+1, n, r, result)  # 递归调用，从 i+1 开始选数
        combination.pop()  # 回溯，撤销选择

n = 5
r = 3
result = []
backtrack([], 1, n, r, result)
print(result)

输出结果为：

[[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]]

其中 result 列表中的每个元素都是一个符合要求的组合。

相关问题

C++编写程序，采用回溯法输出自然数 1~n 中，任取 r 个数的所有组合。（问 题设定，n=5，r=3）代码

以下是 C++ 代码实现：

#include <iostream>
#include <vector>

using namespace std;

void dfs(int n, int r, vector<int>& path, int start) {
    if (path.size() == r) {
        for (int num : path) {
            cout << num << " ";
        }
        cout << endl;
        return;
    }
    for (int i = start; i <= n; i++) {
        path.push_back(i);
        dfs(n, r, path, i + 1);
        path.pop_back();
    }
}

int main() {
    int n = 5, r = 3;
    vector<int> path;
    dfs(n, r, path, 1);
    return 0;
}

回溯法的思路是：对于每一个数字，可以选择将其加入组合或不加入。通过递归实现对所有情况的遍历，最终得到所有符合要求的组合。在实现时，使用一个向量 `path` 记录已经选取的数字，`start` 参数表示当前数字可选的起点，避免重复。

编写程序，采用回溯法输出自然数 1~n 中，任取 r 个数的所有组合。（问 题设定，n=5，r=3）用c++实现

好的，下面给出 C++ 实现代码，与 Python 实现类似：

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& combination, int start, int n, int r, vector<vector<int>>& result) {
    if (combination.size() == r) {
        result.push_back(combination);
        return;
    }
    for (int i = start; i <= n; i++) {
        combination.push_back(i);
        backtrack(combination, i+1, n, r, result);
        combination.pop_back();
    }
}

int main() {
    int n = 5;
    int r = 3;
    vector<vector<int>> result;
    backtrack({}, 1, n, r, result);
    for (const auto& combination : result) {
        for (const auto& num : combination) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

输出结果与 Python 实现一致：

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