企业 网站建设_企业为什么做网站_网络营销网站推广方法_logo设计

题目：

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：解集不能包含重复的子集。

示例:

 输入： nums = [1,2,3]
 输出：
[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]
]

思路：

1. 如果我们需要求{a,b,c}的子集，那么我们需要先求出{a,b}的子集
2. {a,b,c}的子集即为：c分别加入{a,b}的每个子集再加上{a,b}的子集
3. 采用回溯+递归的算法，具体方法是遍历集合的每个元素，对于每个元素，我们可以选择将它加入当前子集或不加入，然后递归地生成所有可能的子集

C语言代码：

/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/// 回溯函数，用于生成子集
void backtrack(int* nums, int numsSize, int start, int* tempList, int tempSize, int*** result, int* returnSize, int** returnColumnSizes) {// 将当前子集添加到结果中(*result) = realloc(*result, (*returnSize + 1) * sizeof(int*));  // 动态扩展结果数组(*result)[*returnSize] = (int*)malloc(tempSize * sizeof(int));  // 分配空间存储子集for (int i = 0; i < tempSize; i++) {(*result)[*returnSize][i] = tempList[i];  // 复制子集内容}*returnColumnSizes = realloc(*returnColumnSizes, (*returnSize + 1) * sizeof(int));  // 动态扩展列大小数组(*returnColumnSizes)[*returnSize] = tempSize;  // 记录当前子集的大小(*returnSize)++;// 遍历后续元素生成子集for (int i = start; i < numsSize; i++) {tempList[tempSize] = nums[i];  // 将当前元素加入子集backtrack(nums, numsSize, i + 1, tempList, tempSize + 1, result, returnSize, returnColumnSizes);  // 通过递序深入}
}// 主函数，生成所有子集
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {*returnSize = 0;  // 初始化子集数量int** result = NULL;  // 存储所有子集*returnColumnSizes = NULL;  // 初始化每个子集大小的数组int* tempList = (int*)malloc(numsSize * sizeof(int));  // 临时数组存储当前子集// 回溯生成子集backtrack(nums, numsSize, 0, tempList, 0, &result, returnSize, returnColumnSizes);free(tempList);  // 释放临时数组return result;  // 返回所有子集
}