Subsets II 🧠
LeetCode Link: Subsets II
Difficulty: Medium
Problem Explanation 📝
Problem: LeetCode 90 - Subsets II
Description: Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.
Intuition: To find all possible subsets of a given array that may contain duplicates, we can use a backtracking approach. The idea is to generate all possible combinations by trying out different elements at each step, while avoiding duplicate subsets. We sort the array to handle duplicates and skip adding duplicate elements to the current subset.
Approach:
- Sort the input array
nums
to handle duplicates and generate combinations in a non-decreasing order. - Initialize an empty vector
subset
to store the current subset. - Initialize an empty vector
result
to store all subsets. - Define a helper function
backtrack
:
- Add the current subset to the
result
vector. - Iterate through the elements in the input array
nums
: - If the current element is a duplicate (not the first occurrence), skip it to avoid duplicate subsets.
- Include the current element in the subset.
- Recursively call
backtrack
with the next index. - Exclude the current element from the subset.
- Call the
backtrack
function with the initial index 0. - Return the
result
vector containing all subsets.
⌛ Time Complexity:
The time complexity is O(2^n), where n is the size of the input array nums
. This is because there are 2^n possible subsets, and we generate all of them.
💾 Space Complexity:
The space complexity is O(n), where n is the size of the input array nums
. This is because we store the subsets in the result
vector.
Solutions 💡
Cpp 💻
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &nums) {
vector<vector<int>> result;
vector<int> subset;
sort(nums.begin(), nums.end()); // Sort the array to handle duplicates
backtrack(nums, 0, subset, result);
return result;
}
private:
void backtrack(const vector<int> &nums, int index, vector<int> &subset, vector<vector<int>> &result) {
result.push_back(subset); // Add the current subset to the result vector
for (int i = index; i < nums.size(); ++i) {
if (i > index && nums[i] == nums[i - 1]) {
continue; // Skip duplicate elements to avoid duplicate subsets
}
subset.push_back(nums[i]); // Include the current element in the subset
backtrack(nums, i + 1, subset, result); // Recursively call with the next index
subset.pop_back(); // Exclude the current element (backtrack)
}
}
};
Python 🐍
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def backtrack(start, subset):
subsets.append(subset[:]) # Append a copy of the current subset
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i - 1]:
continue # Skip duplicates at the same depth level
subset.append(nums[i])
backtrack(i + 1, subset)
subset.pop() # Backtrack
nums.sort() # Sort the input to handle duplicates
subsets = []
backtrack(0, [])
return subsets