[LeetCode]90. Subsets II

Problem

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,
If nums = [1,2,2], a solution is:

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

方法

设定返回的列表的列表为result。先对数组排序，如果nums[i]!=nums[i-1]，那么就遍历result，复制每个列表为tempList，加入nums[i]，然后将该列表加入result中；如果nums[i]==nums[i-1]，那么记录下加入nums[i-1]前返回列表的大小resultIndex，resultSize为加入nums[i-1]后的大小，对result中从resultIndex至resultSize的列表加入nums[i]，然后将新生成的列表加入result

代码

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        nums.sort()
        i = 0
        resultSize = 0
        while i < len(nums):
            num = nums[i]
            resultIndex = 0
            if i>0 and nums[i]==nums[i-1]:
                resultIndex = resultSize;
            resultSize = len(result)
            while resultIndex < resultSize:
                tempList = result[resultIndex][:]
                tempList.append(num)
                result.append(tempList)
                resultIndex += 1
            i += 1
        return result

assert Solution().subsetsWithDup([1,2,2]) == [[],[1],[2],[1,2],[2,2],[1,2,2]]