[LeetCode]题解(python):090 Subsets II

时间:2022-06-23 05:24:08

题目来源


https://leetcode.com/problems/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.

题意分析


Input:

:type nums: List[int]

Output:

   :rtype: List[List[int]]

Conditions:返回一个list的所有子集,注意list中的元素可以是重复的,但是要求返回的子集不重复,子集中的元素顺序为非降序。


题目思路


用dfs,同78题,只是在增加一个子集的时候,判断是否已经存在这个子集再增加。

附注:在扩展子集的时候,可以采用不断增加一个元素,并且先对list进行排序,每次增加时只遍历当前位置之后的元素,这样就可以避免重复。


AC代码(Python)


 class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def dfs(depth, start, valueList):
if valueList not in res:
res.append(valueList)
if depth == len(nums):
return
for i in range(start, len(nums)):
dfs(depth + 1, i + 1, valueList+[nums[i]]) nums.sort()
res = []
dfs(0, 0, [])
return res