class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> ans = new ArrayList<>();
    int n;

    public void dfs(int u, int[] nums){
        if(u == n){
            res.add(new ArrayList<>(ans));
            return ;
        }

        ans.add(nums[u]);
        dfs(u + 1, nums);
        ans.remove(ans.size() - 1);

        while(u + 1 < n && nums[u + 1] == nums[u]) u ++ ;
        dfs(u + 1, nums);
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        n = nums.length;

        dfs(0, nums);

        return res;
    }
}