Subsets II

Question

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],
  []
]

Tags

• Array
• DFS
• Backtracking

Thought

Two solutions:

• Use the for loop to generate the complete subsets and use set to remove the duplicated subsets
• Use the DFS to generate the subsets and remove the duplicated subsets during the DFS process

Codes for these two approaches are provided below.

Suggests to use the second solutions, because it is easier to understand and better to be modified for other different situations.

Code

No DFS

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        resList = [()]
        for num in sorted(nums):
            resList += [tuple(list(item) + [num]) for item in resList]
        resSet = set(resList)
        ans = []
        for item in resSet:
            ans.append(list(item))
        return ans

DFS http://www.cnblogs.com/zuoyuan/p/3758346.html

class Solution:
    # @param num, a list of integer
    # @return a list of lists of integer
    def subsetsWithDup(self, nums):
        def dfs(depth, start, valuelist):
            if valuelist not in res: res.append(valuelist)
            if depth == len(nums): return
            for i in range(start, len(nums)):
                dfs(depth+1, i+1, valuelist+[nums[i]])
        nums.sort()
        res = []
        dfs(0, 0, [])
        return res