题目来源
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