90. 子集 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

做题思路

本题也是回溯类型的题目

并且这道题目很基础也很符合回溯的特征

回溯的代码很简单，只要你把逻辑想清除就行了

---

做回溯的题目都是有套路的

定义一个成员变量，一般都是集合类型

然后一般还都是通过 循环+递归 ，逐个的找出所有的决策阶段并且判断是否符合题目中给出的，如果符合就把这个决策加入到我们一个临时的"path集合"中，进行下一步的判断，通过回溯如果满足了最终的决策阶段，再进行判断，如果满足，就把我们之前加入到 path 里面的所有值都加入到我们之前定义的成员变量集合中。

然后 “回” 继续判断，直到最终结束。

本题是  子集  类型的题目
题目中说有重复的元素
对于这种包含重复元素的求子集的问题是有套路的
我们需要先定义一个Map<Integer，Integer>类型的集合
将题目中所给的数组元素添加到Map中，key就是每一个num，value就是num的个数
之后我们还需要定义两个数组 
int[] counts=new int[map.size()]   int[] unique[]=new int[map.size()];
并且把map集合中存的key和value分别在存入这两个数组中，之后根据这两个数组,在定义
一个 "索引  k" 作为标记
if(k==unique.length)的时候作为满足条件的标志
中间我们还需要定义一个  path集合  存入所有可能情况的子集
当满足条件的时候将这个path集合添加到res集合中，然后继续回溯  

代码实现

class Solution {
    List<List<Integer>> res=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        int[] counts=new int[map.size()];
        int[] numbers=new int[map.size()];
        int k=0;
        for(int num:nums){
            if(map.containsKey(num)){
                counts[k]=map.get(num);
                numbers[k]=num;
                map.remove(num);
                k++;
            }
        }
        backTrack(counts,numbers,0);
        return res;
    }
    public void backTrack(int[] counts,int[] numbers,int k){
        if(k == numbers.length){
            List<Integer> temp=new ArrayList<>();
            temp.addAll(path);
            res.add(temp);
            return;
        }

        for(int i=0;i<=counts[k];i++){
            for(int j=0;j<i;j++){
                path.add(numbers[k]);
            }
            backTrack(counts,numbers,k+1);
            for(int j=0;j<i;j++){
                path.remove(path.size()-1);
            }
        }
    }
}

题目链接

90. 子集 II