Description

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

Submitted Code

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def backtrack(start):
            res.append(path[:])

            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i-1]:
                    continue

                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        nums.sort()
        res = []
        path = []

        backtrack(0)
        return res

Runtime: 0 ms | Beats 100.00%
Memory: 19.36 MB | Beats 88.45%

78. Subsets 문제의 업그레이드 버전이다. 같은 depth(level)에서 중복 숫자가 있을 경우 하나만 선택하지만, 다음 depth에서는 중복 숫자를 허용해야 한다.

nums = [1,2,2]

res = [[],[1],[1,2],[1,2,2],[2],[2,2]]

Other Solutions

1st

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []
        nums.sort()
        
        def create_subset(i):
            if i == len(nums):
                res.append(subset[:])
                return
            
            subset.append(nums[i])
            create_subset(i+1)
            subset.pop()
            
            while i + 1 < len(nums) and nums[i] == nums[i+1]:
                i += 1
                
            create_subset(i+1)
        
        create_subset(0)
        return res

time complexity: 𝑂(2^𝑛)
space complexity: 𝑂(2^𝑛)

include와 exclude를 나누는 binary decision tree 방식이다. 각 숫자마다 subset에 넣을지 안 넣을지 결정하게 되고, 중복 숫자들의 경우 한꺼번에 건너뛰게 된다. for문을 이용한 방법은 현재 상태를 먼저 저장했지만, 이 방법은 끝(leaf)까지 먼저 내려간 뒤 추가되기 때문에 결과 생성 순서가 달라진다.

nums = [1,2,2]

res = [[1,2,2], [1,2], [1], [2,2], [2], []]