[LeetCode]题解（python）：090 Subsets II

题目来源

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）

 1 class Solution(object):
 2     def subsetsWithDup(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: List[List[int]]
 6         """
 7         def dfs(depth, start, valueList):
 8             if valueList not in res:
 9                 res.append(valueList)
10             if depth == len(nums):
11                 return
12             for i in range(start, len(nums)):
13                 dfs(depth + 1, i + 1, valueList+[nums[i]])
14         
15         nums.sort()
16         res = []
17         dfs(0, 0, [])
18         return res