90. Subsets II
1. 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.
2. Example
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
3. Constraints
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
4. Solutions
My Accepted Solution
n = m_nums.size()
Time complexity: O($2^nn$)
Space complexity: O(n)
// backtracking
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int> &m_nums) {
// we must sort the array firstly, which could help us find duplicate elements in O(1) time
sort(m_nums.begin(), m_nums.end());
vector<int> iterSet;
for(int i = 0; i <= m_nums.size(); ++i) {
createSubSet(m_nums, i, 0, iterSet);
}
return subSets;
}
private:
vector<vector<int>> subSets;
void createSubSet(const vector<int> &i_nums, int lengthToCreate, int beginningIndex, vector<int> &m_set) {
if(lengthToCreate == 0) {
subSets.emplace_back(m_set);
return ;
}
for(int i = beginningIndex; i < i_nums.size();) {
m_set.push_back(i_nums[i]);
createSubSet(i_nums, lengthToCreate - 1, i + 1, m_set);
m_set.pop_back();
++i;
while(i < i_nums.size() && i_nums[i] == i_nums[i - 1]) {
// in the same level, we should not use duplicate numbers
// which could result in duplicate sets
// so we use the element for one time and pass all duplicates
++i;
}
}
}
};