题目描述
给定两个整数 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. 回溯法
回溯法是解决组合问题的经典方法,通过递归构建所有可能的组合。
算法步骤:
- 定义一个函数
backtrack(start, path)
,其中start
表示搜索的起点,path
是当前构建的组合。 - 如果当前组合
path
的长度等于k
,将其加入结果集中。 - 遍历从
start
到n
的所有数字:- 将当前数字加入组合。
- 递归构建下一个数字的组合。
- 回溯,移除当前数字。
回溯法的时间复杂度是 O(C(n, k)),其中 C ( n , k ) = n ! k ! ( n − k ) ! C(n, k) = \frac{n!}{k!(n-k)!} C(n,k)=k!(n−k)!n!。
实现代码
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;
}
代码解析
-
动态数组:
- 使用
Array
结构来动态存储组合结果。 initArray
初始化数组,addToArray
动态增加组合。
- 使用
-
回溯函数:
backtrack
函数递归构建所有可能的组合。- 使用
start
控制数字范围,避免重复组合。
-
主函数:
combine
是主函数,调用回溯并返回结果。- 动态分配
returnColumnSizes
以存储每个组合的列数。
-
内存管理:
- 在主函数中释放动态分配的内存,避免内存泄漏。
时间复杂度和空间复杂度
-
时间复杂度:
- 回溯构造所有组合的复杂度是 O(C(n, k)),即 n ! k ! ( n − k ) ! \frac{n!}{k!(n-k)!} k!(n−k)!n!。
-
空间复杂度:
- 临时数组
combination
的空间复杂度为 O(k)。 - 存储结果的空间复杂度为 O ( C ( n , k ) ⋅ k ) O(C(n, k) \cdot k) O(C(n,k)⋅k)。
- 临时数组