F5bd1a76345144bba124144bd5933843
(难度Medium)Problem 90. Subsets II(子集II)

链接

Subsets II - LeetCode

难度等级

Medium

题干

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.

题意

给定一个数组,数组当中可能存在重复的元素。要求返回原数组所能生成的所有不重复的子集。

注意,自己的定义包含空集以及自己。

样例

Example:

**Input:** [1,2,2]
**Output:**
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

题解

我们在之前的78题当中做过了生成所有子集,生成所有子集并不复杂,我们可以通过位运算非常容易地生成。感兴趣的或者之前没有接触的同学可以通过传送门查看:(难度Medium)Problem 78.Subsets(子集) - 小专栏

我们当然可以延续这个思路,先把$2^n$个子集全部生成,然后再过滤掉重复的。但是这里有一个小问题,我们怎么判断重复呢?比较好的办法是把集合使用hash算法hash成一个数,相同hash值的集合代表是相同元素构成的。

且不说hash算法可能存在碰撞,单说这个实现的难度就不小,非常麻烦。而且我们要先算出所有的集合再过滤,再加上hash的开销,会导致时间复杂度非常大。

所以很明显,这道题一定还有更好的解法。

想一下,如果说两个集合是重复的,也就是说集合当中的元素都是完全一样的。那么这两个集合是怎么产生的呢?很简单,必然有一个元素存在两个以上,然后这两个集合各自选了其中不同的部分。说白了,集合的重复是因为元素的重复。

进一步,如果我们想要保证不存在重复的集合,那么我们需要保证相同个数的元素取法应该只有一种。

top Created with Sketch.