LeetCode_87_SubsetsII

1. question: 子集II（中等）

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

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subsets-ii

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10

2. answers

这道题和子集题类似，只不过这道题允许给定的数组中可重复。这样，从去重的角度来看，就和 组合求和II 类似。先对数组排序，这样重复元素只能出现在相邻元素。注意，是同一个位置的元素的不同选择，不能重复；而不是不同位置的元素不能相同（数值）。

因为，为了保证是同一个位置的元素的不同选择，这就需要在回溯操作结束之后，即将进入下个选择的时候，进行判断。代码如下所示：

public class Solution_0086 {

    public List<List<Integer>> result = new ArrayList<>();
    public LinkedList<Integer> group = new LinkedList<>();


    public void generateSet(int[] nums, int startIndex) {

        for (int i = startIndex; i < nums.length; i++) {

            group.add(nums[i]);
            result.add(new ArrayList<>(group));

            // 递归下一个元素
            generateSet(nums, i + 1);

            // 回溯
            group.removeLast();

            // 注意，重复元素的判断是能是不同集合同一位置的判断，也就是一层循环内，所以必须在回溯结束之后，表明接下来是当前元素的下一个选择
            // 注意，当出现重复元素时，是将重复元素中的后面的元素忽略掉。因为只有前面的元素才有可能将重复元素的全部取值遍历完。
            while(i < nums.length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        // 排序
        Arrays.sort(nums);

        generateSet(nums, 0);

        // 空集
        result.add(new ArrayList<>());

        return result;
    }

    public static void main(String[] args) {

//        int[] nums = {1, 2, 2};
        int[] nums = {0};

        Solution_0086 s = new Solution_0086();

        List<List<Integer>> result = s.subsetsWithDup(nums);

        for(List<Integer> list: result) {

            for(Integer i: list)
                System.out.print(i + "\t");

            System.out.println();
        }

    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。