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]] Example 2:

Input: nums = [0] Output: [[],[0]]

Constraints:

1 <= nums.length <= 10 -10 <= nums[i] <= 10

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        Arrays.sort(nums);
        findSubsets(nums, 0, new ArrayList(), res);

        return res;
    }

    public void findSubsets(int[] nums, int i, List<Integer> list, List<List<Integer>> res) {
        int n = nums.length;
        if(i==n){
            res.add(new ArrayList(list));
            return;
        }

        // pick ith element into subset
        list.add(nums[i]);
        findSubsets(nums, i+1, list, res);
        list.remove(list.size()-1);

        // don't pick ith element into subset, while skipping the duplicates
        while( (i+1)<n && (nums[i] == nums[i+1]) )     // first array must be sorted 
            i++;                             // skipping duplicates indices
        findSubsets(nums, i+1, list, res);
    }

}