90. 子集 II

题目地址(90. 子集 II)

https://leetcode-cn.com/problems/subsets-ii/

题目描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 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 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集

关键点

• “树层去重”和“树枝去重”非常重要。

代码

• 语言支持：Java

Java Code:

class Solution {
        ArrayList<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        //定义一个用于判断是否遍历过的列表
        Boolean[] used;
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            //先排序 将可能相等的数据排列在一起
            Arrays.sort(nums);
            //舒适化 默认是false
            used = new Boolean[nums.length];
            loop(nums, 0);
            return res;
        }
        void loop(int[] nums ,int startIndex){
            res.add(new ArrayList<>(path));
            for (int i = startIndex; i < nums.length ; i++) {
                //这里搞晕了 以为是used[i] == used[i - 1] emmm
                //如果当前数和上一个数字相等 并且used[i-1]=false说明是同层遇到了相同的数字 见循环最后一条 used[i] = false;
                // 接下来是同一层的下一次循环 所以这里就不可以再次读取了
                //如果当前数和上一个数字相等 但是used[i-1]=true 说明是在递归前就赋上了true值 是在递归的子树中相同 这种情况就可以选取
                if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                    continue;
                }
                //上面说过了 递归前将used[i]= true 递归后再改回来 就可以只在同层上判断是否重复了
                used[i]= true;
                path.add(nums[i]);
                loop(nums, i + 1);
                path.removeLast();
                used[i] = false;
            }
        }
    }

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=yFxlC)
• 空间复杂度：#card=math&code=O%28n%29&id=iRYbQ)