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

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

解题方法

与subsets 1相比，要去掉重复的subsets,因为我们已经sort过，所以可以方便地去掉。 如果当前的number在之前已经用过dfs过，那么当前的dfs结果一定被包含了，所以可以直接跳过。

Solution

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        results = []
        if not nums:
            return [[]]
        nums.sort()
        self.subsetsHelper(results, nums, 0, [])
        return results

    def subsetsHelper(self, results, nums, index, curList):
        tmpList = list(curList)
        results.append(tmpList)

        for i in range(index, len(nums)):
            if i != index and nums[i] == nums[i-1]:
                continue
            curList.append(nums[i])
            self.subsetsHelper(results, nums, i + 1, curList)
            curList.pop()

Reference