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.
Example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Solution
- DFS + 剪枝
- 每次循环删掉已经加入到vector的元素
(Subsets2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution(object):
def subset_helper(self, nums, result, vector):
result.append(vector[:])
for i in range(len(nums)):
# duplicated
if i>0 and nums[i] == nums[i-1]:
continue
vector.append(nums[i])
self.subset_helper(nums[i+1:],result,vector)
vector.pop()
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
if nums == None:
return result
self.subset_helper(sorted(nums), result,[])
return result
|