首页 > 代码库 > 90. Subsets II
90. Subsets II
https://leetcode.com/problems/subsets-ii/#/description
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: 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], [] ]
Sol 1:
Iteration.
Sort first.
class Solution(object): def subsetsWithDup(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ # iterately res = [[]] nums.sort() for num in nums: res += [item + [num] for item in res if item + [num] not in res] return res
Sol 2:
DFS.
class Solution(object): def subsetsWithDup(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ # DFS res = [] nums.sort() self.dfs(nums, 0, [], res) return res def dfs(self, nums, index, path, res): res.append(path) for i in range(index, len(nums)): if i > index and nums[i] == nums[i-1]: continue self.dfs(nums, i+1, path+[nums[i]], res)
Similar question:
78. Subsets
90. Subsets II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。