90. Subsets II

MediumLeetCode

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1

Input: nums = [1,2,2]

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2

Input: nums = [0]

Output: [[],[0]]

Constraints

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

How to solve the problem

• Backtracking (DFS)

Code

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        path = []
        result = []
        nums.sort()  # Only a sorted list can ensure no duplicated set

        def backtracking(startIndex):
            result.append(path[:])
            coveredSet = set()
            for i in range(startIndex, len(nums)):
                if nums[i] in coveredSet:
                    continue
                coveredSet.add(nums[i])
                path.append(nums[i])
                backtracking(i + 1)
                path.pop()

        backtracking(0)
        return result

Complexity

• Time complexity: O(2^n * n)
• Space complexity: O(n)