[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）

 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

巴特西

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

最新文章

热门文章