温岭 网站建设,计算机软件开发培训,wordpress+开发入门,网站效果给定两个整数n和k#xff0c;返回范围[1,n]中所有可能的k个数的组合。 你可以按任何顺序返回答案。 示例1#xff1a; 输入#xff1a;n 4, k 2
输出#xff1a;
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
] 示例2#xff1a; 输入#xff1a;n 1, k 1
输出#xff1a… 给定两个整数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 201 k n void backTracking(int n, int k, int startIndex, int* returnSize, int* count, int* path, int** result){// 当path里元素数量等于指定的k说明找到一个集合将其添加到result中并返回if((*count) k){result[*returnSize] (int*)malloc(sizeof(int) * k);for(int i 0; i k; i){result[*returnSize][i] path[i];}(*returnSize);return;}/*剪枝前i n剪枝后i n - (k - *count) 1我们的目标是找到每一条路径因此path里的元素一定为k而我们是从i向后顺序遍历的这就要求i后面的元素至少要有 k-*count 个元素即最多遍历到 n-(k-*count)1(包括i) 就不需要往后遍历了因为后续元素不足了*/// 遍历给定的数组以startIndex作为起始元素防止出现出现重复集合for(int i startIndex; i n - (k - *count) 1; i){// 每遍历到一个元素将其加入pathpath[(*count)] i;// 递归调用函数backTracking(n, k, i 1, returnSize, count, path, result);// 回溯将path数组的最上层元素弹出(*count)--;}
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {// result存储所有集合int** result (int**)malloc(sizeof(int*) * 200000);// path存储单一集合int* path (int*)malloc(sizeof(int) * k);// 初始集合数量为0*returnSize 0;// startIndex为每次遍历的起始元素count是path数组里的元素数量int startIndex 1, count 0;// 调用回溯函数backTracking(n, k, startIndex, returnSize, count, path, result);// returnColumnSizes记录所有集合的大小并全部赋值k*returnColumnSizes (int*)malloc(sizeof(int) * (*returnSize));for(int i 0; i *returnSize; i){(*returnColumnSizes)[i] k;}// 返回结果return result;
}///https://leetcode.cn/problems/combinations/solutions/3081998/cyu-yan-hui-su-jian-zhi-hou-fu-xiang-xi-5d66c/ 代码随想录(参考)
