回溯法 有n个数，输出其中r(r<=n)个数的所有组合代码

以下是回溯法求解输出r个数的所有组合的代码：

def combination(nums, r):
    def backtrack(start, path):
        if len(path) == r:
            res.append(path[:])
            return
        for i in range(start, n):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    n = len(nums)
    res = []
    backtrack(0, [])
    return res

其中，nums表示原始数组，r表示要输出的组合中元素的个数。

回溯算法的框架如下：

- 确定回溯函数的参数：在这里，我们需要传入一个起始位置start和一个路径path，表示从nums[start]开始往后选数，并且已经选了path中的元素。
- 确定终止条件：当path中的元素个数等于r时，说明已经找到了一个符合条件的组合，把它加入结果集res中，并返回。
- 确定回溯过程：从start开始往后遍历原始数组nums，每次选择一个数加入path中，并从下一个位置递归调用回溯函数backtrack。递归返回后，需要将path中最后一个元素弹出，继续遍历nums后面的元素。

在主函数中，调用回溯函数backtrack并返回结果集res即可。

相关问题

Java回溯法实现：问题描述:找出从自然数1，2，…，n中任取r个数的所有组合。 问题描述:找出从自然数1，2，…，n中任取r个数的所有组合. 将找到的组合以从小到大顺序存于a[0]. a[1],"，a[r-1]中，组合的元素满足以下性质:(1) 将找到的组合以从小到大顺序存于a[0].A[1]，“，a[r-1]中，组合的元素满足以下性质：(1) a[i+1]>a0，后一个数字比前一个大;c(2)a[i]-i<=n-r+1。c A[i+1]>a0，后一个数字比前一个大；c(2)a[i]-i<=n-r+1。

Java代码实现如下，使用回溯法：

public class Combination {
    public static void main(String[] args) {
        int n = 5, r = 3;
        int[] a = new int[r];
        combination(a, 0, 1, n, r);
    }

    public static void combination(int[] a, int m, int start, int n, int r) {
        if (m == r) {
            for (int i = 0; i < r; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = start; i <= n; i++) {
            a[m] = i;
            if (m == 0 || (a[m] > a[m - 1] && a[m] - m <= n - r + 1)) {
                combination(a, m + 1, i + 1, n, r);
            }
        }
    }
}

其中，combination方法中，m表示当前已经选了几个数，start表示从哪个数开始选，n表示可选的最大数，r表示要选几个数。a数组存储已经选好的数。每次递归从start开始往后选，保证了每个组合中的数都是按从小到大的顺序排列的。在选数的过程中，根据题目的要求，进行剪枝，即如果当前选的数比前一个数小或者选的数与下标之和大于n-r+1，则不再继续向下递归。最终输出所有符合要求的组合。

回溯法的思想是搜索所有可能的解，每次搜索到一个解时，回溯到上一步继续搜索。这种方法可以解决一些组合、排列等问题，但是时间复杂度较高，需要注意剪枝等优化方法。

按照回溯法的思想，将找到的组合以从小到大的顺序存放到数组a[0],a[1]， . a[r-1]中，组合中的元素满足以下性质: (1) a[i+1]>a[i], 即后一个数大于前个数; (2) a[i]-i<=n-r+1。C语言实现

以下是一个基于回溯法的C语言实现，实现了按照从小到大的顺序存放组合的要求，同时满足了题目中给出的两个性质：

#include <stdio.h>

#define MAX_N 100
#define MAX_R 100

int n, r;
int a[MAX_R];

void backtrack(int x) {
    if (x == r) {
        for (int i = 0; i < r; i++) {
            printf("%d ", a[i]);
        }
        printf("\n");
    } else {
        for (int i = (x == 0 ? 1 : a[x-1]+1); i <= n-r+x+1; i++) {
            a[x] = i;
            backtrack(x+1);
        }
    }
}

int main() {
    scanf("%d%d", &n, &r);
    backtrack(0);
    return 0;
}

其中，函数`backtrack(x)`表示已经选定了前`x`个数，要从剩余的数中选出后面的数。如果`x`等于`r`，说明已经选够了`r`个数，可以输出组合。

在每一次递归中，我们从剩余的数中选取一个数，将其存放在数组`a`的第`x`个位置，然后递归调用`backtrack(x+1)`，继续选下一个数。

值得注意的是，在选第一个数时，我们需要从1开始选取。在选取后面的数时，为了满足性质(1)，我们需要从上一个选中的数的下一个数开始选取。为了满足性质(2)，我们需要保证当前选中的数减去它在数组`a`中的下标不超过`n-r+1`。

希望这个代码能够帮助到你！