class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // sorting to skip over duplicate elements during recursion
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();

        findSubsetsWithDuplicates(nums, 0, result, temp);
        return result;
    }

    public void findSubsetsWithDuplicates(int[] nums, int index, List<List<Integer>> result, List<Integer> temp)
    {
        // base condition
        if(index == nums.length)
        {
            result.add(new ArrayList<>(temp));
            return;
        }


        // take the current element into the subset
        temp.add(nums[index]);
        findSubsetsWithDuplicates(nums, index+1, result, temp);

        // do not take the current element into the subset
        temp.remove(temp.size()-1);

        // Skip all duplicates of the current number
        while(index+1 < nums.length && nums[index] == nums[index+1])
            index++;
        
        findSubsetsWithDuplicates(nums, index+1, result, temp);
    }
}