Sponsored
Sponsored
In this approach, the problem of subsets with duplicates is solved by first sorting the array. This assists in easily identifying and omitting duplicates. The backtracking method is utilized to construct all possible subsets, ensuring no duplicate subsets are generated by skipping duplicate numbers during recursive backtracking.
The time complexity of this solution is O(2^n * n) due to the number of subsets (2^n) and time taken to convert each subset to the result. The space complexity is O(n), where n is the length of the array, due to the space required for the subset building.
1#include <stdio.h>
2#include <stdlib.h>
3
4// Compare function for qsort
5int cmp(const void *a, const void *b) {
6 return (*(int *)a - *(int *)b);
7}
8
9void backtrack(int *nums, int numsSize, int **results, int *resultSizes, int *columnSizes, int *temp, int tempSize, int start, int *returnSize) {
10 // Allocate memory for current subset and add it to the results
11 resultSizes[*returnSize] = tempSize;
12 results[*returnSize] = malloc(resultSizes[*returnSize] * sizeof(int));
13 for (int i = 0; i < tempSize; ++i) results[*returnSize][i] = temp[i];
14 (*returnSize)++;
15
16 for (int i = start; i < numsSize; ++i) {
17 if (i > start && nums[i] == nums[i - 1]) continue; // Skip duplicates
18 temp[tempSize] = nums[i];
19 backtrack(nums, numsSize, results, resultSizes, columnSizes, temp, tempSize + 1, i + 1, returnSize);
20 }
21}
22
23int **subsetsWithDup(int *nums, int numsSize, int *returnSize, int **returnColumnSizes) {
24 int maxSize = 1 << numsSize;
25 int **results = malloc(maxSize * sizeof(int *));
26 *returnColumnSizes = malloc(maxSize * sizeof(int));
27 int *temp = malloc(numsSize * sizeof(int));
28 *returnSize = 0;
29
30 qsort(nums, numsSize, sizeof(int), cmp);
31 backtrack(nums, numsSize, results, *returnColumnSizes, *returnColumnSizes, temp, 0, 0, returnSize);
32
33 free(temp);
34 return results;
35}
36
37int main() {
38 int nums[] = {1, 2, 2};
39 int size = sizeof(nums) / sizeof(nums[0]);
40 int returnSize;
41 int *returnColumnSizes;
42 int **result = subsetsWithDup(nums, size, &returnSize, &returnColumnSizes);
43
44 for (int i = 0; i < returnSize; ++i) {
45 printf("[");
46 for (int j = 0; j < returnColumnSizes[i]; ++j) {
47 printf("%d%c", result[i][j], j == returnColumnSizes[i] - 1 ? ' ' : ', ');
48 }
49 printf("]\n");
50 free(result[i]);
51 }
52 free(result);
53 free(returnColumnSizes);
54 return 0;
55}The solution uses a sorting-based backtracking method. The array is sorted to handle duplicates easily. A recursive backtracking function is used to generate subsets. Before adding a number to the current subset, we check whether it is a duplicate of the previously considered number in the same recursion level. This avoids generating duplicate subsets.
This approach iteratively constructs the power set by extending previously generated sets with each new number. During the process, duplicates are skipped by comparing the current number with the previous one. This ensures subsets generated in each iteration are unique.
The time complexity is O(2^n * n); space is O(2^n * n) as it iteratively builds the power set using subsets directly.
1#include
The C solution utilizes iterative sets through a sorted array. It dynamically expands the subsets using the current number while bypassing duplicates by monitoring the indices of additions, skipping similar additions through index boundaries.