公司网站服务器选择,合优人才网合川,北京网站策划公司,梵克雅宝戒指给你一个整数数组 nums #xff0c;其中可能包含重复元素#xff0c;请你返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。返回的解集中#xff0c;子集可以按 任意顺序 排列。
思路一#xff1a;回溯
int comp(const void* a, cons…给你一个整数数组 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]直接跳过处理即可
