专栏首页Petrichor的专栏leetcode: 90. Subsets II

leetcode: 90. Subsets II

Problem

# Given a collection of integers that might contain duplicates, nums, 
# return all possible subsets (the power set).
#
# Note: 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],
#     []
# ]

Idea

1. 由于不可重,因此需要先对x做sort(),以保证后面简单地通过“not in”即可完成去重;
2. 每次对现有子集做一份 拷贝;
3. 从x中选定一个数,后插入 该拷贝中的所有样本 尾部;
4. 拷贝集 参照原子集,进行去重;
5. 将拷贝集 并入 原子集。

leetcode: 78. Subsets

AC

DFS:

class Solution():
    def subsetsWithDup(self, x):
        if not x:
            return [[]]
        else:
            x.sort()
            tmp = self.subsetsWithDup(x[:-1])
            res = tmp + [i+[x[-1]] for i in tmp if i+[x[-1]] not in tmp]
            return res

迭代:

class Solution():
    def subsetsWithDup(self, x):
        x.sort()    # 需要先sort,因为list中就算元素相同,只要先后顺序不一样,就无法去重
        res = [[]]
        for i in range(len(x)):
            for j in range(len(res)):
                if res[j]+[x[i]] not in res:    # 去重查验
                    res.append(res[j]+[x[i]])
        return res


if __name__ == "__main__":
    assert Solution().subsetsWithDup([1, 2, 2]) == [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode: 40. Combination Sum II

    JNingWei
  • leetcode: 96. Unique Binary Search Trees

    JNingWei
  • leetcode: 50. Pow(x, n)

    JNingWei
  • 画解算法:盛最多水的容器 | 腾讯面试编程50题(二)

    题目:给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i,...

    double
  • 【python-leetcode56-区间合并】合并区间

    输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6]...

    绝命生
  • nodejs的hello world的详解

    前面几篇介绍过nodejs的第一个项目!这篇系统的介绍一下第一个nodejs项目

    十月梦想
  • web storage和cookie的区别

    IT故事会
  • SaaS面临盈利挑战 平台之争北森胜算几何?

    SaaS从2003年引入中国,一直是被惯以低端软件小微企业的代名词,2007迎来了Saas时代的巅峰时期,2008后SaaS开始一泻千里,2014年后受资本市场...

    人称T客
  • Android系统启动——6 SystemServer启动

    SystemServer是Android系统的核心之一,大部分Android提供的服务都运行在这个进程里,SystemServer中运行的服务总共有60多种。为...

    隔壁老李头
  • .Net轻松实现支付宝服务窗网页授权并获取用户相关信息

     最近在开发一个商业街区的聚合扫码支付功能,其中需要用到的有支付宝,微信两种支付方式,当然对于开发微信支付而已作为自己的老本行已经比较熟悉了,然而对于我来说支...

    追逐时光者

扫码关注云+社区

领取腾讯云代金券