如何将固定层数嵌套for循环改递归，实现任意r值的n选r组合枚举

实现思路 #

• 用临时数组存储当前已经选中的组合元素
• 递归每一层负责选中第k个位置的元素，要求该元素必须大于上一层选中的元素，避免生成重复的组合
• 当递归深度等于r时，说明已经选够了r个元素，直接输出当前组合即可

完整可运行代码 #

#include <stdio.h>
// 递归辅助函数
void comb_helper(int n, int r, int depth, int prev, int *curr_comb) {
    // 递归终止：已经选够r个元素，输出
    if (depth == r) {
        for (int i = 0; i < r; i++) {
            printf("%d ", curr_comb[i]);
        }
        printf("\n");
        return;
    }
    // 当前层可选范围：从prev+1开始，到n - 剩余需选个数 +1，保证后续有足够元素可选
    int remain = r - depth;
    for (int i = prev + 1; i <= n - remain + 1; i++) {
        curr_comb[depth] = i;
        // 进入下一层递归
        comb_helper(n, r, depth + 1, i, curr_comb);
    }
}

void make_combination(int n, int r) {
    // 非法参数直接返回
    if (r <= 0 || r > n) return;
    // 变长数组存储当前组合，C99及以上标准支持，不支持的环境可改为动态内存申请或固定长度数组
    int curr_comb[r];
    comb_helper(n, r, 0, 0, curr_comb);
}

int main(void){
    int n, r;
    printf("Insert n : ");
    scanf("%d", &n);
    printf("Insert r : ");
    scanf("%d", &r);
    make_combination(n, r);
    return 0;
}

说明 #

• 该实现的时间复杂度和固定层数for循环一致，为O(C(n,r))，无冗余计算
• 已内置边界判断，可兼容r>n、r<=0等非法输入场景

内容的提问来源于stack exchange，提问作者Jaeman Lee