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.
1from typing import List
2
3def subsetsWithDup(nums: List[int]) -> List[List[int]]:
4 def backtrack(start: int, path: List[int]):
5 result.append(path.copy())
6 for i in range(start, len(nums)):
7 if i > start and nums[i] == nums[i - 1]:
8 continue
9 path.append(nums[i])
10 backtrack(i + 1, path)
11 path.pop()
12
13 nums.sort()
14 result = []
15 backtrack(0, [])
16 return result
17
18# Example Usage
19d = subsetsWithDup([1, 2, 2])
20for subset in d:
21 print(subset)This Python solution also uses sorting followed by a recursive backtracking method to eliminate duplicate subsets. It accomplishes this by checking and skipping duplicates.
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.
1using System;
using System.Collections.Generic;
class Solution {
public IList<IList<int>> SubsetsWithDup(int[] nums) {
Array.Sort(nums);
IList<IList<int>> result = new List<IList<int>>();
result.Add(new List<int>());
int start, newSize = 0;
for (int i = 0; i < nums.Length; i++) {
start = (i > 0 && nums[i] == nums[i - 1]) ? newSize : 0;
newSize = result.Count;
for (int j = start; j < newSize; j++) {
List<int> current = new List<int>(result[j]);
current.Add(nums[i]);
result.Add(current);
}
}
return result;
}
public static void Main(string[] args) {
Solution solution = new Solution();
var result = solution.SubsetsWithDup(new int[] { 1, 2, 2 });
foreach (var subset in result) {
Console.WriteLine("[" + string.Join(", ", subset) + "]");
}
}
}The C# solution demonstrates the iterative construction of subsets with comprehensive steps to handle duplicates. Through controlled loops and sorted arrays, the formation of subsets is stabilized, ensuring unique additions.