子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

思路

针对数组的每一个数有‘取’与‘不取’两种情况，如下图

image.png

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> L = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        Arrays.sort(nums);
        subset(nums, L, list, 0);
        return L;
    }
    
    public static void subset(int[] nums, List<List<Integer>> L, List<Integer> list, int index) {

        if (index == nums.length) {
            for (int i = 0; i < L.size(); i++) {
                if (L.get(i).equals(list)) {
                    return;
                }
            }
            L.add(new ArrayList(list));

            return ;
        }

        list.add(nums[index]);
        subset(nums, L, list, index + 1);
        list.remove(list.size() - 1);
        subset(nums, L, list, index + 1);
    }
}

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> L = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        HashSet<List<Integer>> set = new HashSet<List<Integer>>();
        Arrays.sort(nums);
        subset(nums, set, list, 0);

        return new ArrayList<List<Integer>>(set);
    }
    
    public static void subset(int[] nums, HashSet<List<Integer>> set, List<Integer> list, int index) {

        if (index == nums.length) {
            set.add(new ArrayList(list));
            return ;
        }

        list.add(nums[index]);
        subset(nums, set, list, index + 1);
        list.remove(list.size() - 1);
        subset(nums, set, list, index + 1);
    }
}