品牌建设卓有成效_b2b免费商务_济南seo优化公司助力排名_优化模型

力扣第90题：带重复元素的子集

问题描述

给定一个整数数组nums，该数组可能包含重复元素。返回该数组所有可能的子集（幂集），并且子集中的元素需要去重。返回的子集中的每个元素应按照非递减顺序排列。

例如，对于输入数组 [1, 2, 2]，应返回：

[[], [1], [1,2], [1,2,2], [2], [2,2]]

思路与算法

这道题的核心是生成所有子集，并且确保在存在重复元素的情况下，跳过重复的子集。我们可以使用 回溯算法 来实现这一点。

1. 排序

首先，我们对数组 nums 进行排序。这样一来，我们可以在生成子集时，跳过相同的元素，避免重复生成相同的子集。

2. 回溯

我们可以通过回溯来生成所有的子集。每次选择一个元素，将其加入到当前的子集中，并递归生成后续的子集。递归的过程中，当遇到重复的元素时，我们跳过它们，从而避免生成重复的子集。

3. 空间管理

每当找到一个子集时，我们需要将其存储起来。为了存储所有的子集，我们使用二维数组 result。此外，我们还需要一个一维数组 returnColumnSizes 来记录每个子集的大小。

代码实现

以下是代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 回溯函数生成所有子集 
void backtrack(int* nums, int numsSize, int** result, int* returnColumnSizes, int* subset, int subsetSize, int start, int* returnSize) { // 创建一个当前子集的副本 result[*returnSize] = (int*)malloc(subsetSize * sizeof(int)); for (int i = 0; i < subsetSize; i++) { result[*returnSize][i] = subset[i]; } returnColumnSizes[*returnSize] = subsetSize; (*returnSize)++; // 继续生成子集 for (int i = start; i < numsSize; i++) { // 跳过重复的元素 if (i > start && nums[i] == nums[i - 1]) { continue; } subset[subsetSize] = nums[i]; backtrack(nums, numsSize, result, returnColumnSizes, subset, subsetSize + 1, i + 1, returnSize); } 
} int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { // 排序，确保重复元素可以被跳过 qsort(nums, numsSize, sizeof(int), (int(*)(const void*, const void*))strcmp); int maxSubsets = 1 << numsSize; // 子集总数是 2^n int** result = (int**)malloc(maxSubsets * sizeof(int*)); *returnColumnSizes = (int*)malloc(maxSubsets * sizeof(int)); *returnSize = 0; int* subset = (int*)malloc(numsSize * sizeof(int)); // 临时存储一个子集 backtrack(nums, numsSize, result, *returnColumnSizes, subset, 0, 0, returnSize); free(subset); return result; 
} // 打印二维数组
void printSubsets(int** result, int* returnColumnSizes, int returnSize) {for (int i = 0; i < returnSize; i++) {printf("[");for (int j = 0; j < returnColumnSizes[i]; j++) {printf("%d", result[i][j]);if (j < returnColumnSizes[i] - 1) {printf(", ");}}printf("]\n");}
}int main() {int nums[] = {1, 2, 2};int numsSize = sizeof(nums) / sizeof(nums[0]);int returnSize = 0;int* returnColumnSizes = NULL;int** result = subsetsWithDup(nums, numsSize, &returnSize, &returnColumnSizes);printSubsets(result, returnColumnSizes, returnSize);// 释放内存for (int i = 0; i < returnSize; i++) {free(result[i]);}free(result);free(returnColumnSizes);return 0;
}

代码解释

1. backtrack 函数

backtrack 是核心的递归回溯函数。它用于生成所有的子集。

• 输入参数：

  • nums：输入数组，包含整数元素。
  • numsSize：nums 的大小。
  • result：二维数组，用于存储生成的所有子集。
  • returnColumnSizes：一维数组，用于存储每个子集的大小。
  • subset：临时数组，用于存储当前子集。
  • subsetSize：当前子集的大小。
  • start：搜索的起始索引。
  • returnSize：当前已生成的子集数量。

• 算法：

  • 将当前子集存储到 result 中。
  • 递归生成子集，从 start 索引开始，避免重复元素。
  • 在递归过程中，通过 if (i > start && nums[i] == nums[i - 1]) 来跳过重复元素。

2. subsetsWithDup 函数

subsetsWithDup 函数是主函数，它首先对输入数组进行排序，以确保可以跳过重复的元素。然后，它调用 backtrack 函数来生成所有子集。

• 输入参数：

  • nums：输入的整数数组。
  • numsSize：数组的大小。
  • returnSize：用来返回子集的数量。
  • returnColumnSizes：用来返回每个子集的大小。

• 算法：

  • 排序 nums 数组。
  • 使用 backtrack 递归生成所有子集。
  • 最后，返回存储所有子集的二维数组 result。

3. 内存管理

• 每次创建一个新的子集时，我们通过 malloc 动态分配内存。递归结束后，result 中的每个子集都需要释放内存。

4. printSubsets 函数

printSubsets 用于打印生成的所有子集。每个子集打印时，按照子集中的元素顺序输出，子集之间用逗号分隔。

时间复杂度分析

• 排序数组的时间复杂度为 $O(n\log n)$，其中 $n$ 是数组的大小。
• 回溯生成子集的时间复杂度为 $O(2^n)$，因为总共有 $2^n$ 个子集需要生成。
• 因此，整体时间复杂度为 $O(n\log n+2^n)$。