力扣leetcode 77 - 组合 C语言解法 递归+回溯

题目：

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

思路：

这道题要求返回从范围 [1, n] 中任意选择 k 个数的所有组合，经典解法是使用回溯算法。回溯时需要注意：

1. 递归终止条件是当前组合长度达到 k。
2. 每次选择数字时，按顺序递增，避免重复。
3. 用动态数组存储结果，注意内存分配和释放。

代码如下：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
// 辅助函数：递序生成组合
void backtrack(int n, int k, int start, int* temp, int tempSize, int** result, int* returnSize, int* returnColumnSizes) {
    if (tempSize == k) { // 终止条件：当前组合长度达到 k
        result[*returnSize] = (int*)malloc(k * sizeof(int)); // 分配内存存储当前组合
        for (int i = 0; i < k; i++) {
            result[*returnSize][i] = temp[i];
        }
        returnColumnSizes[*returnSize] = k; // 记录当前组合的长度
        (*returnSize)++;
        return;
    }

    for (int i = start; i <= n; i++) {
        temp[tempSize] = i; // 选择当前数字
        backtrack(n, k, i + 1, temp, tempSize + 1, result, returnSize, returnColumnSizes); // 递序选择下一个数字
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    int maxCombinations = 1; // 计算最大组合数 C(n, k)
    for (int i = 0; i < k; i++) {
        maxCombinations *= (n - i);
        maxCombinations /= (i + 1);
    }

    int** result = (int**)malloc(maxCombinations * sizeof(int*)); // 分配存储所有组合的数组
    *returnColumnSizes = (int*)malloc(maxCombinations * sizeof(int)); // 分配存储每个组合长度的数组
    *returnSize = 0;

    int* temp = (int*)malloc(k * sizeof(int)); // 临时数组存储当前组合
    backtrack(n, k, 1, temp, 0, result, returnSize, *returnColumnSizes);

    free(temp); // 释放临时数组内存
    return result;
}