Problem Statement

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.

Example 1:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Problem Link

Subsets II - LeetCode

Code

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        
        vector<vector<int>> res;
        vector<int> temp;
        sort(nums.begin(),nums.end());
        backtrack(res,temp,nums,0);
        return res;
    }
    
    void backtrack(vector<vector<int>> &res,vector<int> &temp,vector<int>& nums,int start)
    {
        for(int i=start;i<nums.size();i++)
        {
           
            temp.push_back(nums[i]);
            
            
            backtrack(res,temp,nums,i+1);
            temp.pop_back();
             **while(i+1<nums.size()&&nums[i]==nums[i+1])//skip duplicates
                i++;//can also be placed above temp.pop_back()**
            
        }
        res.push_back(temp);
    }
};

Complexity Analysis:

• Time Complexity: O(2 ^ n).For every index i two recursive case originates, So Time Complexity is O(2^n).
• Space Complexity: O(n).The space complexity can be reduced if the output array is not stored and the static and global variable is used to store the output string.