90. Subsets II

# Medium

For this problem, [1, 4] and [4, 1] are the same subsets

Solution:

1. Sort the list to let same numbers be neighborhood.

2. Very similar to #78.

3. Add if inside the adding level process.

Time complexity = T_mergeSort + T_subsets = $O(NlgN) + O(n*2^n) = O(n*2^n)$

Space complexity = $O(n*2^n)$

java

class Solution {
    public List<List<Integer>> res = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        helper(nums, new ArrayList<Integer>(), 0);
        return res;
    }
    
    public void helper(int[] nums, ArrayList<Integer> level, int i) {
        res.add(new ArrayList<Integer>(level));
        if(i == nums.length) return;
        
        for(int j = i; j < nums.length; j ++) {
            if(j > i && nums[j] == nums[j-1])
                continue;
            level.add(nums[j]);
            helper(nums, level, j + 1);
            level.remove(level.size() - 1);
        }
    }
}