前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 题目解析之 Subsets II

Leetcode 题目解析之 Subsets II

原创
作者头像
ruochen
发布2022-01-10 20:10:12
1.3K0
发布2022-01-10 20:10:12
举报
文章被收录于专栏:若尘的技术专栏

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.

The solution set must not contain duplicate subsets.

For example,

If nums = 1,2,2, a solution is:

[

2,

1,

1,2,2,

2,2,

1,2,

[]

]

使用二进制,不需要递归。对于二进制中的每一位,0表示不选择,1表示选择。则有2^n种情况。

使用HashSet,能够直接过滤重复情况(先对数组排序,题目中也要求每个list非降序排列)。

代码语言:txt
复制
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null) {
            return null;
        }
        if (nums.length == 0) {
            return new ArrayList<List<Integer>>();
        }
        Set<List<Integer>> set = new HashSet<List<Integer>>();
        // 题目中要求每个list是非降序,所以要先从小到大排序
        Arrays.sort(nums);
        // 对于n位,有2^n种情况
        for (int i = 0; i < Math.pow(2, nums.length); i++) {
            List<Integer> list = new ArrayList<Integer>();
            int tmp = i;
            // 对于每种情况,分别求得二进制中1的个数
            // 0代表不选择,1代表选择
            for (int j = 0; j < nums.length; j++) {
                int bit = tmp & 1;
                tmp >>= 1;
                if (bit == 1) {
                    list.add(nums[j]);
                }
            }
            set.add(list);
        }
        return new ArrayList<List<Integer>>(set);
    }

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档