90.Subsets II

Tags: [recursion], [set], [combination], [brute_force], [sort]

Com: {fb}

Link: https://leetcode.com/problems/subsets-ii/#/description

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

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

More clear solution: Combination

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return [[]]

        nums.sort()
        result = [[]]
        buff = []
        self.subsets_with_dup_helper(nums, 0, buff, result)
        return result

    def subsets_with_dup_helper(self, nums, index, buff, result):
        while index < len(nums):
            curr = nums[index]
            buff.append(curr)
            result.append(list(buff))
            self.subsets_with_dup_helper(nums, index + 1, buff, result)
            buff.pop()

            # find the next elem, which != curr
            index += 1
            while index < len(nums) and nums[index] == curr:
                index += 1

Revelation:

• Sorting is for easy to skip the duplicates.

Note:

• Time complexity = O(n!), n is the number of elements of the given nums.

Solution: Combination, Set

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return [[]]

        nums.sort()
        result = [[]]
        buff = []
        self.subsets_with_dup_helper(nums, 0, buff, result)
        return result

    def subsets_with_dup_helper(self, nums, index, buff, result):
        elems_set = set()
        for i in xrange(index, len(nums)):
            curr = nums[i]
            if curr in elems_set:
                continue
            elems_set.add(curr)

            buff.append(curr)
            result.append(list(buff))
            self.subsets_with_dup_helper(nums, i + 1, buff, result)

            buff.pop()

Question:

• I still not very understand why the above algorithm need sort the nums. If we don't sort the nums, it will give out the wrong result.
• The elems_set here means, for the current subset (which is contained by buff), we will not put the same value element on the one position.

Answer:

• Using the case: nums[2, 1, 2] to run the above code with nums.sort(), you will see why the sorting is necessary.

Note:

• Time complexity = O(n!), n is the number of elements of the given nums. Because given n elements, there will be O(n!) subsets.