编写程序，采用回溯法输出自然数 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 列表中的每个元素都是一个符合要求的组合。

相关问题

用Java编写一个实验程序，采用回溯法输出自然数1~ n 中任取 r 个数的所有组合。

好的，以下是回溯法输出自然数1~n中任取r个数的所有组合的Java代码：

import java.util.ArrayList;
import java.util.List;

public class CombinationGenerator {
    public static void main(String[] args) {
        int n = 5; // 自然数1~n
        int r = 3; // 任取r个数
        List<List<Integer>> combinations = generateCombinations(n, r);
        System.out.println("自然数1~" + n + "中任取" + r + "个数的所有组合：");
        for (List<Integer> combination : combinations) {
            System.out.println(combination);
        }
    }

    private static List<List<Integer>> generateCombinations(int n, int r) {
        List<List<Integer>> combinations = new ArrayList<>();
        List<Integer> currentCombination = new ArrayList<>();
        backtrack(combinations, currentCombination, 1, n, r);
        return combinations;
    }

    private static void backtrack(List<List<Integer>> combinations, List<Integer> currentCombination, int start, int n, int r) {
        if (currentCombination.size() == r) {
            combinations.add(new ArrayList<>(currentCombination));
            return;
        }
        for (int i = start; i <= n; i++) {
            currentCombination.add(i);
            backtrack(combinations, currentCombination, i + 1, n, r);
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}

代码中的 `generateCombinations` 方法接受两个参数：`n` 表示自然数1~n，`r` 表示任取r个数。它返回一个 `List<List<Integer>>` 对象，其中每个 `List<Integer>` 对象表示一种组合。代码中使用了回溯法来生成所有组合。具体来说，我们从1开始遍历到n，将每个数都加入当前组合中，然后递归地向后遍历，直到组合的长度达到r。如果当前组合的长度等于r，则将它加入结果集中，然后回溯到上一个状态，继续遍历下一个数。

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` 参数表示当前数字可选的起点，避免重复。