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;
    }
}
Subsets II
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


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;

};
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;
    }
};