leetcode做题笔记90. 子集 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode做题笔记90. 子集 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

思路一：回溯

int comp(const void* a, const void* b) {
  return *(int*)a - *(int*)b;
}
 void backtracking(int* nums, int numsSize, int** res, int* returnSize, int** returnColumnSizes, 
                  int* path, int pathSize, int startIndex) {
    res[*returnSize] = (int*)malloc(sizeof(int) * pathSize);
    memcpy(res[*returnSize], path, sizeof(int) * pathSize);
    (*returnColumnSizes)[*returnSize] = pathSize;
    (*returnSize)++;
    for (int i = startIndex; i < numsSize; i++) {
        
        path[pathSize] = nums[i];
        backtracking(nums, numsSize, res, returnSize, returnColumnSizes, path, pathSize + 1, i + 1);
        while (i < numsSize - 1 && nums[i] == nums[i + 1]) i++; 
    }
}

int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    *returnColumnSizes = (int*)malloc(sizeof(int) * 10001);
    int** res = (int**)malloc(sizeof(int*) * 10001);
    int* path = (int*)malloc(sizeof(int) * numsSize);
    qsort(nums, numsSize, sizeof(int), comp); 
    backtracking(nums, numsSize, res, returnSize, returnColumnSizes, path, 0, 0);
    return res;
}