[LeetCode] 90. Subsets II

90. Subsets II

Medium

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

---

문제 풀이

문제 접근

1. 숫자들의 길이가 작기 때문에, 백트랙킹으로 풀 수 있을 것 같다. 

풀이

1. 순열을 구해야 한다.
2. 주의할 점은 여기서 중복을 허용하지 않는다. 
3. 예를 들어, 2 1 2 가 있을때 2 1 과 1 2 는 중복이 된다.
4. 그리고 정답을 잘 보면, 순서는 상관없지만 정답들이 정렬이 되어있다. 
5. 리스트 정렬을 하고나서 순열을 백트래킹으로 구하면 된다.
6. 시간을 줄이기 위해서 다음 숫자가 지금이랑 같은 경우도 패스해준다.

• 시간복잡도가 N * N^2 이다.
  쉽게 설명하자면 부분 집합을 만들때마다 숫자가 하나 추가되면, 최악의 경우에는 부분 집합이 2의 n승으로 늘어난다. 
  1 : [] 1 > 2개 
  1 2 : [] 1 2 12 > 4개
  1 2 3 : [] 1 2 3 12 13 23 123 > 8개 

소스 코드

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = [set()]
        n = len(nums)
        nums.sort()
        def rec(index, temp):
            for i in range(index, n):
                if i != index and nums[i] == nums[i - 1]: continue
                temp.append(nums[i])
                if temp not in res:
                    res.append(temp.copy())
                rec(i + 1, temp)
                temp.pop()
        rec(0, [])
        return res