90.子集II

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        //排序后便于去重
        Arrays.sort(nums);
        dfs(0,nums,ans,list);
        return ans;
    }

    private void dfs(int begin,int[] nums,List<List<Integer>> ans,List<Integer> list){
        ans.add(new ArrayList<>(list));
        for(int i = begin;i<nums.length;i++){
            //去重
            if(i > begin && nums[i] == nums[i-1]){
                continue;
            }
            list.add(nums[i]);
            dfs(i+1,nums,ans,list);
            list.remove(list.size()-1);
        }
    }
}