Subsets II

Given a list of numbers that may has duplicate numbers, return all possible subsets

Notice

Each element in a subset must be in non-descending order.

The ordering between two subsets is free.

The solution set must not contain duplicate subsets.

Example

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

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

Solution:

这道题容易犯错的地方就是，忘记了一开始排序，然后就是删除临时变量最后一个元素的时候写错了删除nums数组。

class Solution:
    """
    @param S: A set of numbers.
    @return: A list of lists. All valid subsets.
    """
    def subsetsWithDup(self, nums):
        # write your code here
        result = []
        nums.sort()
        self. dfs(nums, result, [], 0)
        return result

    def dfs(self, nums, result, current, pos):
        if current not in result:
            result.append(list(current))
        for i in range(pos, len(nums)):
            current.append(nums[i])
            self.dfs(nums, result, current, i + 1)
            del current[-1]