商城网站建设讯息,wdcp 防盗链 网站不能打开,小程序头条小游戏,厨师培训题目描述
给定两个整数 n 和 k#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按任意顺序返回答案。 示例
示例 1
输入#xff1a;
n 4, k 2输出#xff1a;
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]示例 2
输入#xff1a;
n 1, k …题目描述
给定两个整数 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)。
