专栏首页木又AI帮【leetcode刷题】20T46-子集 II

【leetcode刷题】20T46-子集 II


木又同学2020年第46篇解题报告

leetcode第90题:子集 II

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


【题目】

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

【思路】

设置存储当前递归传入的集合,表示子集(称为目前集合),开始遍历的下标start。

从start开始遍历所有元素,如果当前元素和前一个元素相同,则该元素不加入到目前集合进行递归;否则,该元素加入到目前集合,并存入结果,进行递归(开始遍历的下标改为该元素的下标+1)。

举例来说,对于[1, 2, 2],目前集合为空集[],开始遍历下标为0

1)遍历第0个元素,目前集合为[1],设置遍历下标为1,递归遍历(可以得到[1, 2], [1, 2, 2]);

2)遍历第1个元素,目前集合为[2],设置变量下标为2,递归遍历(可以得到[2, 2]);

3)遍历第2个元素,元素和前一个元素相同,不进行递归。

因此,所有可能为[[], [1], [1, 2], [1, 2, 2], [2], [2,2]]。

【代码】

python版本

class Solution(object):
    def add_elements(self, nums, start, current, res):
        for i in range(start, len(nums)):
            if i == start or nums[i] != nums[i - 1]:
                tmp = copy.copy(current)
                tmp.append(nums[i])
                res.append(tmp)
                self.add_elements(nums, i + 1, tmp, res)

    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = [[]]
        nums.sort()
        self.add_elements(nums, 0, [], res)
        return res

C++版本

class Solution {
public:
    void get_subset(vector<int>& nums, int start, vector<int> current, vector<vector<int>>& res) {
        for (int i = start; i < nums.size(); i++) {
            if (i == start || nums[i] != nums[i - 1]) {
                current.push_back(nums[i]);
                res.push_back(current);
                get_subset(nums, i + 1, current, res);
                current.pop_back();
            }
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> current;
        res.push_back(current);
        sort(nums.begin(), nums.end());
        get_subset(nums, 0, current, res);
        return res;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T23-最大矩形

    Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle con...

    木又AI帮
  • 【leetcode刷题】T38-存在重复元素 III

    Given an array of integers, find out whether there are two distinct indices i an...

    木又AI帮
  • 【leetcode刷题】T34-只出现一次的数字 II

    Given a non-empty array of integers, every element appears three times except fo...

    木又AI帮
  • LeetCode 78. Subsets

    ShenduCC
  • Explain详解与索引最佳实践

    使用EXPLAIN关键字可以模拟优化器执行SQL语句,从而知道MySQL是 如何处理你的SQL语句的。分析你的查询语句或是结构的性能瓶颈

    DencyCheng
  • Intent.FLAG_ACTIVITY_CLEAR_TOP与SingleTask的区别

    在测试Activity的启动过程中,测试Intent.FLAG_ACTIVITY_CLEAR_TOP以及SingleTask的过程中发现这两者有一些区别。

    None_Ling
  • 2-1 是否同一棵二叉搜索树 (35 分)

    给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插...

    韩旭051
  • C++核心准则E.13: 直接拥有一个对象所有权时永远不要抛出异常

    E.13: Never throw while being the direct owner of an object

    面向对象思考
  • 东方有戏精?企点来「除妖」

    ? 想必大家的朋友圈已经被年会神曲「释放自我·东方有戏精2.0」刷屏,一曲改编自「沙漠骆驼」的歌曲吐槽了大家工作中遇到的奇葩事情。 看完大家都在感叹「这唱的就...

    腾讯企点
  • mall在Windows环境下的部署

    1.关于IDEA的安装与使用具体参考https://github.com/judasn/IntelliJ-IDEA-Tutorial

    macrozheng

扫码关注云+社区

领取腾讯云代金券