LeetCode 90. Subsets II.jpg
LeetCode 90. Subsets II
Description
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题的递进题.
- 此题求给定数组的所有可能的子集，与78题不同，此题给定的数据可能有重复.
- 我们首先对给定的数组排序，然后如果当前元素与前一个元素相同，我们跳过进行下一步.
- 基本思路同78题完全一致.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2018-12-25 21:24:06
# @Last Modified by: 何睿
# @Last Modified time: 2018-12-25 21:41:42
import copy
class Solution:
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = [[]]
nums = sorted(nums)
self.recursion(res, [], nums, 0, len(nums))
return res
def recursion(self, res, path, nums, start, end):
if start == end:
return
for i in range(start, end):
if i != start and nums[i] == nums[i-1]:
continue
else:
path.append(nums[i])
res.append(copy.deepcopy(path))
self.recursion(res, path, nums, i+1, end)
path.pop()
if __name__ == "__main__":
so = Solution()
res = so.subsetsWithDup([1, 1, 6, 2])
print(res)
