力扣第 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)$。