Subsets II

题目

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

Note:The solution set must not contain duplicate subsets.

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

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

思路分析

这道题跟上面一道题Subsets一样感觉要穷举所nums数组中所有的数才能够得到子数组，然后加上题目中又要求return all posible subsets, 基本可以判断这道题会用到DFS，这是做这道题的初步的思路分析。

这道题的数组中添加了重复的元素，所以在找子数组的时候要考虑去掉重复的子数组的问题，因此需要对回溯函数进行一定的剪枝，对于排列组合的模板程序，剪枝通常可以从两个地方出发，一是在返回结果result.append之前进行剪枝，另一个则是在list.append处剪枝，具体使用哪一种需要视情况而定，哪种简单就选谁。

在做这道题的时候第一印象还是用set来进行去重，其实这就陷入了一个误区。set的元素不能是数组，这样就不能通过set来进行去重了，要怎样才能去重呢？这道题去重的手段就是对于相同的数字只用计算出前面一个的子集比如，对于[1, 1]，我们只用求出前面一个1的所有子集:

• 排序数组使数值一样的元素相邻地排在一起

• 如果某位置元素和前一位置数值相同了，即nums[i] = nums[i – 1]，那么就跳过该位置。通过 i>Index 来判断当前 i 是否是当前子集的出发位置还是后面位置。

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        subsets = []
        self.dfs(sorted(nums), 0, [], subsets)
        return subsets

    def dfs(self, nums, index, path, subsets):
        subsets.append(path)
        for i in xrange(index, len(nums)):
            if i>index and nums[i] == nums[i-1]: continue
            self.dfs(nums, i+1, path+[nums[i]], subsets)

复杂度分析

时间复杂度

通过DFS递归实现的时间复杂度公式为：O(构造解的复杂度 * 解的个数)。每次递归里面有个for循环，所以每次构造解需要O(n)时间，那么总共有多少的解呢，2^n个，所以可以计算出总的时间复杂度为O(n*2^n)

空间复杂度

空间复杂度跟解的个数（递归调用的个数）是一直的，所以是O(2^n)