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.

&nbsp;
Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Example 2:
Input: nums = [0]
Output: [[],[0]]

&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 10
	-10 &lt;= nums[i] &lt;= 10


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = []
        nums.sort()
        def subset(p, up):
            if len(up) == 0:
                if p not in ans:
                    ans.append(p)
                return 
            ch = up[0]
            subset(p+[ch], up[1:])
            subset(p, up[1:])
        subset([], nums)
        return ans
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // Sort the input array to handle duplicates properly
        Arrays.sort(nums);
        // Start the recursion with an empty prefix list
        return subset(new ArrayList<Integer>(), nums);
    }
    
    // Recursive function to generate subsets
    public List<List<Integer>> subset(ArrayList<Integer> prefix, int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        
        // Base case: If there are no elements in nums, add the current prefix to result
        if (nums.length == 0) {
            result.add(new ArrayList<>(prefix));
            return result;
        }
        
        // Include the first element of nums in the prefix
        ArrayList<Integer> withCurrent = new ArrayList<>(prefix);
        withCurrent.add(nums[0]);
        
        // Recursive call with the first element included
        List<List<Integer>> left = subset(withCurrent, Arrays.copyOfRange(nums, 1, nums.length));
        
        List<List<Integer>> right = new ArrayList<>();
        
        // Check for duplicates in the prefix and decide whether to include the first element again
        if (prefix.size() > 0 && prefix.get(prefix.size() - 1) == nums[0]) {
            // If the current element is a duplicate, don't include it in the prefix
            // This avoids generating duplicate subsets
        } else {
            // If the current element is not a duplicate, include it in the prefix
            right = subset(prefix, Arrays.copyOfRange(nums, 1, nums.length));
        }
        
        // Combine the subsets with and without the current element
        left.addAll(right);
        return left;
    }
}
class Solution {
public:
    vector<vector<int>> ans;
    void recur(vector<int>& nums, int i, vector<int> vec){
        if(i > nums.size()){
            return;
        }
        for(int j = i; j < nums.size(); j++){
            vec.push_back(nums[j]);

            vector<int> temp = vec;
            sort(vec.begin(), vec.end());

            if(find(ans.begin(), ans.end(), vec) == ans.end()){
                ans.push_back(vec);
            }

            recur(nums, j + 1, vec);

            //can't just pop_back any need to pop_back the one we added
            vec = temp;
            vec.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> vec;
        ans.push_back(vec);
        recur(nums, 0, vec);

        return ans;
    }
};
var subsetsWithDup = function(nums) {
    let result = [];
    //sort the nums to avoid duplicates;
    nums.sort((a,b) => a -b);
    result.push([]);

    let startIdx = 0;
    let endIdx = 0;

    for(let i =0; i<nums.length; i++){
        let current = nums[i];
        startIdx = 0;

        //check for duplicates and get the idx of last subset
        if(i> 0 && nums[i] === nums[i-1]){
            startIdx = endIdx +1;
        }
        endIdx = result.length - 1;

        for(let j = startIdx; j< endIdx+1; j++){
            let set1 = result[j].slice(0);
            set1.push(current);
            result.push(set1);
        }
    }

    return result;

};
Subsets II