18. Subsets II

Description

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Each element in a subset must be in non-descending order.

The ordering between two subsets is free.

The solution set must not contain duplicate subsets.

Example

Example 1:

Input: [0]

Output:

[

  [],

  [0]

]

Example 2:

Input: [1,2,2]

Output:

[

  [2],

  [1],

  [1,2,2],

  [2,2],

  [1,2],

  []

]

Challenge

Can you do it in both recursively and iteratively?

思路：

这个题与subset那个题类似，唯一的区别是可能有重复的数，那么关键就在于如何去重， 拿[1, 2, 2]举例， 当subset是[1]时，会希望第一个[2]被加进去成为[1, 2]但是到第二个2的时候就需要跳过，不然会有两个[1, 2], 但是subset是[1, 2]的时候，第二个2又是需要的，这样我们就得出去重的条件，如果一个数等于它前面一个数，并且前面一个数没有被加进subset的话，那么它也不应该被加进去。

代码：