leetcode 【 Subsets II 】python 实现

题目：

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

[

  [2],

  [1],

  [1,2,2],

  [2,2],

  [1,2],

  []

]

代码：oj测试通过 Runtime: 78 ms

 class Solution:

     # @param num, a list of integer

     # @return a list of lists of integer

     def dfs(self, start, S, result, father_elements):

         if father_elements in result:

             return

         result.append(father_elements)

         for i in range(start, len(S)):

             self.dfs(i+1, S, result, father_elements+[S[i]])

     def subsetsWithDup(self, S):

         # none case

         if S is None:

             return []

         # deep first search

         result = []

         first_depth = {}

         self.dfs(0, sorted(S), result, [])

         return result

思路：

大体思路跟Subsets差不多，详情见：

http://www.cnblogs.com/xbf9xbf/p/4253208.html

只需要每次向result中添加子集时注意判断一下这个子集是否已经存在。如果存在那么就直接返回，不做处理。

巴特西

leetcode 【 Subsets II 】python 实现

最新文章

热门文章