力扣第 77 题 组合

题目描述

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

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

示例

示例 1

输入：

n = 4, k = 2

输出：

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

示例 2

输入：

n = 1, k = 1

输出：

[[1]]

解题思路

1. 回溯法

回溯法是解决组合问题的经典方法，通过递归构建所有可能的组合。

算法步骤：

1. 定义一个函数 backtrack(start, path)，其中 start 表示搜索的起点，path 是当前构建的组合。
2. 如果当前组合 path 的长度等于 k，将其加入结果集中。
3. 遍历从 start 到 n 的所有数字：
   • 将当前数字加入组合。
   • 递归构建下一个数字的组合。
   • 回溯，移除当前数字。

回溯法的时间复杂度是 O(C(n, k))，其中 $C(n,k)=\frac{n!}{k!(n-k)!}$。

实现代码

C语言实现

#include <stdio.h>
#include <stdlib.h>

// 动态数组结构
typedef struct {
    int** data;
    int size;
    int capacity;
} Array;

void initArray(Array* arr, int capacity) {
    arr->data = (int**)malloc(sizeof(int*) * capacity);
    arr->size = 0;
    arr->capacity = capacity;
}

void addToArray(Array* arr, int* combination, int k) {
    if (arr->size == arr->capacity) {
        arr->capacity *= 2;
        arr->data = (int**)realloc(arr->data, sizeof(int*) * arr->capacity);
    }
    arr->data[arr->size] = (int*)malloc(sizeof(int) * k);
    for (int i = 0; i < k; i++) {
        arr->data[arr->size][i] = combination[i];
    }
    arr->size++;
}

void backtrack(int n, int k, int start, int* combination, int combSize, Array* result) {
    if (combSize == k) {
        addToArray(result, combination, k);
        return;
    }
    for (int i = start; i <= n; i++) {
        combination[combSize] = i;
        backtrack(n, k, i + 1, combination, combSize + 1, result);
    }
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    Array result;
    initArray(&result, 16);
    int* combination = (int*)malloc(sizeof(int) * k);
    backtrack(n, k, 1, combination, 0, &result);

    *returnSize = result.size;
    *returnColumnSizes = (int*)malloc(sizeof(int) * result.size);
    for (int i = 0; i < result.size; i++) {
        (*returnColumnSizes)[i] = k;
    }

    free(combination);
    return result.data;
}

int main() {
    int n = 4, k = 2;
    int returnSize;
    int* returnColumnSizes;

    int** combinations = combine(n, k, &returnSize, &returnColumnSizes);

    printf("Combinations:\n");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", combinations[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(", ");
        }
        printf("]\n");
        free(combinations[i]); // 释放每个组合的内存
    }

    free(combinations); // 释放结果数组的内存
    free(returnColumnSizes); // 释放列大小数组的内存

    return 0;
}

代码解析

1. 动态数组：

   • 使用 Array 结构来动态存储组合结果。
   • initArray 初始化数组，addToArray 动态增加组合。

2. 回溯函数：

   • backtrack 函数递归构建所有可能的组合。
   • 使用 start 控制数字范围，避免重复组合。

3. 主函数：

   • combine 是主函数，调用回溯并返回结果。
   • 动态分配 returnColumnSizes 以存储每个组合的列数。

4. 内存管理：

   • 在主函数中释放动态分配的内存，避免内存泄漏。

时间复杂度和空间复杂度

• 时间复杂度：

  • 回溯构造所有组合的复杂度是 O(C(n, k))，即 $\frac{n!}{k!(n-k)!}$。

• 空间复杂度：

  • 临时数组 combination 的空间复杂度为 O(k)。
  • 存储结果的空间复杂度为 $O(C(n,k)\cdot k)$。