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.
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class Solution {
6 public List<List<Integer>> subsetsWithDup(int[] nums) {
7 Arrays.sort(nums);
8 List<List<Integer>> result = new ArrayList<>();
9 backtrack(result, new ArrayList<>(), nums, 0);
10 return result;
11 }
12
13 private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
14 result.add(new ArrayList<>(tempList));
15 for (int i = start; i < nums.length; i++) {
16 if (i > start && nums[i] == nums[i - 1]) continue; // skip duplicates
17 tempList.add(nums[i]);
18 backtrack(result, tempList, nums, i + 1);
19 tempList.remove(tempList.size() - 1);
20 }
21 }
22
23 public static void main(String[] args) {
24 Solution solution = new Solution();
25 int[] nums = {1, 2, 2};
26 List<List<Integer>> result = solution.subsetsWithDup(nums);
27 for (List<Integer> subset : result) {
28 System.out.println(subset);
29 }
30 }
31}This Java solution sorts the array initially to help in skipping duplicates effectively. The backtracking method is implemented to recursively build subsets, ensuring duplicates are bypassed by checking for equality with the preceding element.
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 <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> result = {{}}, newSets;
size_t start = 0, newSize;
for (size_t i = 0; i < nums.size(); ++i) {
start = (i > 0 && nums[i] == nums[i - 1]) ? newSize : 0;
newSize = result.size();
newSets.clear();
for (size_t j = start; j < newSize; ++j) {
newSets.push_back(result[j]);
newSets.back().push_back(nums[i]);
}
result.insert(result.end(), newSets.begin(), newSets.end());
}
return result;
}
};
int main() {
Solution solution;
std::vector<int> nums = {1, 2, 2};
std::vector<std::vector<int>> result = solution.subsetsWithDup(nums);
for (const auto& subset : result) {
std::cout << "[";
for (size_t i = 0; i < subset.size(); ++i) {
std::cout << subset[i] << (i + 1 < subset.size() ? ", " : "");
}
std::cout << "]\n";
}
return 0;
}In the C++ solution, the input array is sorted to streamline the identification of duplicates. Subsets are iteratively generated, and a dynamic size adjustment ensures duplicates from the immediate previous addition are controlled.