C++: Subsets II

Thought Process

To generate all unique subsets of a given array (which may contain duplicates), we use backtracking. First, we sort the array to group duplicates together. During the backtracking process, we skip duplicate elements to avoid redundant subsets. This ensures that we generate all unique subsets efficiently. 

class Solution {
public:

    void backTrack(vector<vector<int>> &ans, vector<int> &tmp, vector<int> nums, int start){

        ans.push_back(tmp);

        for(int i=start;i<nums.size();i++){

            if(i>start && nums[i]==nums[i-1])
                continue;
            tmp.push_back(nums[i]);
            backTrack(ans,tmp,nums,i+1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> tmp;
        sort(nums.begin(),nums.end());

        backTrack(ans,tmp,nums,0);
        return ans;
    }
};

Code Complexity

Time Complexity: O(2n)

The algorithm generates all possible subsets of the input array, resulting in 2n subsets, where 'n' is the size of the input. Sorting adds an additional O(n log n).

Space Complexity: O(n)

The recursion stack depth is proportional to the size of the input('n'), and the temporary vector stores intermediate results.

Code copied!