090._subsets_ii.md

90. Subsets II

题目： https://leetcode.com/problems/subsets-ii/

难度 : Medium

思路：

参考别人的

现在来观察规律，与之前有不同之处是我们需要一个位置来mark，因为不再需要往之前出现过的地方再加了，看这个:

[[],[1]] 是 [1] 的子集合
[[],[1],[2],[1,2]] 是 [1,2] 的子集合，实际上就是1的子集合们加了一个2
新来的2不能再从头开始加了，它需要从[ .., [2],[1,2] ]加 才是合理的

****当出现多个重复数字时，应该从 已经拥有了新数字所出现全部次数的list开始加才是合理的****
[[],[1]] 是 [1] 的子集合
[[],[1],[2],[1,2]] 是 [1,2] 的子集合，实际上就是1的子集合们加了一个2
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
] 是 [1,2,2] 的子集和，实际上也就是[1,2]的子集合加了一个2
新来的2不能再从头开始加了，它需要从[ .., [2,2],[1,2,2] ]加 才是合理的
例如：

这里这个start是来记录了之前一次数组的长度，temp_size记住目前数组的长度，然后用这个来达到去重的目的，非常聪明

自己的解法

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        results = [[]]
        for i in range(len(nums)):
            if any(nums[i] in result for result in results):
                results.extend([result + [nums[i]] for result in results if result.count(nums[i]) == i - nums.index(nums[i])])
            else:
                results.extend([result + [nums[i]] for result in results])
        return results
        

别人的，但是一个意思

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = [[]]
        temp_size = 0
        for i in range(len(nums)):
        	start = temp_size if i >= 1 and nums[i] == nums[i-1] else 0
        	temp_size = len(result)
        	for j in range(start, temp_size):
        		result.append(result[j] + [nums[i]])
        return result