90. Subsets II

题目描述

Given a collection of integers that might contain duplicates,nums, return all possible subsets.

Note:The solution set must not contain duplicate subsets.

For example,
Ifnums=[1,2,2], a solution is:

解题方法

    public List<List<Integer>> subsetsWithDup(int[] nums){
        List<List<Integer>> lists = new ArrayList<>();
        //corner case
        if(nums == null || nums.length == 0){
            return lists;
        }

        Arrays.sort(nums); //skip the duplicates
        helper(nums, 0 , new ArrayList<Integer>(), lists);
        return lists;
    }

    private void helper(int[] nums, int start, List<Integer> list, List<List<Integer>> lists){
        lists.add(new ArrayList<>(list));
        for(int i = start; i < nums.length; i++){
            if(i > start && nums[i] == nums[i - 1]){
                continue;
            }
            list.add(nums[i]);
            helper(nums, i + 1, list, lists);
            list.remove(list.size() - 1);
        }
    }