90. Subsets II

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

Solution:

Since we have duplicates in the nums array, we have to be careful with finding the unique subsets.

The basic idea is that sort and only process the first unique pass of dfsVisit recursion calls

1. sort array to have duplicate numbers be next to each other
2. we process the first passes (i == start) of all DFS visits. That is the first unique encounter of every number (duplicated later or not)
3. For later passes in the same dfsVisit recursion sub-call (namely, during for loop, if i != start), if the nums[i] is the same as previous number, then it means, we process the same combination already in the first pass.

class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        n = len(nums)
        res = [[]]

        for i in range(n):
            if i != 0 and nums[i] == nums[i-1]:
                continue
            self.dfsVisit(i + 1, nums, res, [nums[i]])

        return res

    def dfsVisit(self, start, nums, res, cur):
        if start > len(nums):
            return
        res.append(cur[:])

        for i in range(start, len(nums)):
            if i != start and nums[i] == nums[i-1] :
                continue
            self.dfsVisit(i + 1, nums, res, cur + [nums[i]])

Time Complexity: O( $$2^n$$ )

because each element in the given array has 2 options: either be in the subset or not.

For array of size n, you have 2 * 2 * 2 ... * 2 of n times, thus 2^n