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;
}

分析：

本题与78子集问题很像，只需在78代码的基础上考虑数字重复问题即可，对于数字重复可先将数组内数组排序一遍再加上while (i < numsSize - 1 && nums[i] == nums[i + 1]) i++;这行代码即可解决

总结：

本题考察回溯的应用，考虑重复数字，对于nums[i] == nums[i + 1]直接跳过处理即可