当前位置: 首页 > biancheng >正文

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<IntegerInteger>类型的集合
将题目中所给的数组元素添加到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

相关文章:

  • switch循环语句
  • 牛客练习赛#84 F 莫比乌斯反演+杜教筛+技巧+斐波那契数列和gcd的结论+矩阵快速幂
  • ZZNUOJ_用C语言编写程序实现1342:支配值数目(附完整源码)
  • java毕业设计后勤管理系统餐饮评价监督系统(附源码、数据库)
  • 前端基础学习笔记
  • 【TS】联合类型--类型断言--类型推断
  • 谈笑风声的秘密
  • QT影城网上售票系统
  • NetCDF数据在ArcMap中的使用
  • 打怪升级(考验思路)