https://leetcode.com/problems/subsets-ii/
Subsets II
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], [] ]
Idea:
Initialize the return list, `res`, with a list of an empty list, since any set will have empty set as one of its subset. You need to sort the numbers first, because you are asked to give non-descending order subsets.
Then, starting from the first number in the sorted list, you compare the current number with the previous number. If they are different (or the current number is the first number you scan), you need to concatenate the current number with all existing subsets in `res`. If the current number is the same as the previous number, the current number has no need to concatenate with all previous subsets. It will introduce duplication if you do so. Instead, you only need to concatenate the current number with the subsets that have been added into `res` by the previous same number. For example, if the previous number is 2, and it introduces [2], [1,2] into the `res` by concatenating with [] and [1]. Then, the current number being 2 will only need to append new subsets [2,2] and [1,2,2] by concatenating with [2] and [1,2]. However, it is not needed to concatenate with [] and [1] again.
Code:
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = [[]]
nums.sort()
for i in xrange(len(nums)):
if len(res) == 1 or nums[i] != nums[i-1]:
l = len(res)
for j in xrange(len(res)-l, len(res)):
res.append(res[j] + [nums[i]])
return res