Leetcode 90. Subsets II - Python

Leetcode 90 문제 보기

 

문제 이해하기

주어진 nums는 중복된 원소가 존재가능한 숫자들의 리스트다.

nums에서 얻을 수 있는 부분집합들을 구하되, 부분집합들은 중복되어선 안된다.

이 때 출력 순서는 상관없다.

 

아이디어 구상

가장 먼저 떠오른 생각은, 우선 조합을 모두 구한 후 set을 취해 중복을 제거하는 방법이다.

nums의 길이가 최대 10까지 가능한만큼, 심플하면서도 성능도 나쁘지 않을 것이다.

 

하지만 학습의 목적을 위해 조금 다른 방법도 생각해보자.

 

본 문제는 LeetCode 40번과 거의 유사한 문제다.

LeetCode 40번 보기

마찬가지로 중복되는 조합을 제외해야하므로 약간의 트릭이 필요하다.

 

하나의 원소를 포함시키는 경우와, 그 원소와 같은 값의 원소들은 전부 제외시키는 경우,

위 2가지 경우로 가지를 뻗어나가자.

그렇게 되면 중복되는 조합이 생성되는 것을 미연에 방지하며 결과 리스트에 담을 수 있을 것이다.

이를 위해서는 우선 nums가 정렬이 되어야 쉽게 풀이가 가능하다.

 

test case가 [1, 2, 2]인 Decision Tree를 그리며 생각해보자.

By Mesotes

 

위와 같은 논리로 탐색을 진행하다가 Leaf node를 만났을 경우, 결과 리스트에 담아주면 되겠다.

 

이 때의 시간복잡도는 어떻게 될까?

n = len(nums)라 할 경우, 최악의 경우 O(2 ^ n),

여기에 각 조합을 연산해야하므로 최악의 경우 최종적으로 Time Complexity ~ O(n * (2 ^ n))일 것이다.

 

그러나 현실적으로 각 부분집합의 크기는 n보다 작은 경우가 대부분이고 Backtracking을 적절히 해주기 때문에 실제 시간복잡도는 이보다 나을 것으로 생각된다.

 

풀이

정답을 담을 리스트를 선언하고 nums를 정렬한다.

res = []
nums.sort()

 

dfs()는 다음과 같다.

다음 index의 원소가 이전의 값과 같다면 skip하고 다시 탐색을 진행한다.

탐색하며 만나는 값들은 res에 담아준다.

res.append(cur[:])
            
prev = -11 # -10 <= nums[i] <= 10
for i in range(idx, len(nums)):
    if prev == nums[i]:
        continue
    cur.append(nums[i])
    dfs(cur, i + 1)
    cur.pop()
    prev = nums[i]

 

전체 코드는 다음과 같다.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        
        def dfs(cur, idx):
            res.append(cur[:])
            
            prev = -11 # -10 <= nums[i] <= 10
            for i in range(idx, len(nums)):
                if prev == nums[i]:
                    continue
                cur.append(nums[i])
                dfs(cur, i + 1)
                cur.pop()
                prev = nums[i]
            
        dfs([], 0)
        return res

 

---

Leetcode 90. Subsets II

https://leetcode.com/problems/subsets-ii/​

​

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다