Leetcode 78. Subsets - Python

Leetcode 78 문제 보기

 

문제 이해하기

주어진 숫자 리스트 nums의 원소들을 이용하여 생성가능한 부분 집합(the power set)을 출력하라.

이 때 가능한 집합들의 출력은 어떤 순서로 해도 상관없다.

 

아이디어 구상

온라인 코딩 테스트에서는 조합을 생성하는 라이브러리를 활용해서 쉽게 구하도록 하자.

파이썬의 경우, itertools를 활용하면 된다.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        for i in range(len(nums)+1):
            res += list(itertools.combinations(nums, i))
            
        return res

 

이제 직접 알고리즘을 구현해보자.

반복문을 이용한 iterative한 방법, 재귀를 통한 recursive한 방법 등 다양한 방법으로 문제를 풀 수 있다.

그 중 DFS를 활용한 재귀 방식이 이해하기 쉽고 직관적이다.

 

By Mesotes

 

[1, 2, 3]일 때의 Decision Tree를 그려보자.

각각의 원소는 subset에 1)추가될 수 있고, 2)추가되지 않을 수 있다.

따라서 Decision Tree의 오른편에는 원소가 추가되지 않을 경우, 왼편에는 하나의 원소가 추가될 경우를 그려본다.

 

최종적으로 얻어지는 2 ^ (len(nums)) 개의 leaf node들이 구하고자 하는 부분집합들이 된다.

 

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

len(nums) == n이라 했을 때, 부분집합의 가짓수는 (2 ^ n)개다.

이 때 각각의 부분집합 생성을 위해 O(n)의 연산이 요구된다.

따라서 최악의 경우 Time Complexity ~ O(n * (2 ^ n)) 가 예상된다.

 

풀이

정답을 담을 리스트와 각각의 부분집합을 담을 리스트를 준비한다.

res = []
subset = []

 

dfs()의 base case는 다음과 같다.

만약 leaf node에 도달했다면, 즉, index == len(nums)일 때 return한다.

 

이 때 subset을 res에 copy해야한다.

순열을 그대로 append하지 않고 copy를 하는 이유는 앞선 포스팅에서 설명한 바 있다.

Leetcode 46. Permutations 풀이-base case 참조

if i == len(nums):
    res.append(subset[:])
    return

 

dfs()의 재귀 부분은 다음과 같다.

우선 nums의 원소 하나를 subset에 추가하고, 다음 index에 대해 dfs()를 실행한다. (추가될 경우)

이후 추가했던 원소를 subset에서 제거하고, 다시 다음 index에 대해 dfs()를 진행한다. (제외될 경우)

subset.append(nums[i])
dfs(i + 1)

subset.pop()
dfs(i + 1)

 

전체 코드는 다음과 같다.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []
        
        def dfs(i):
            # base case
            if i == len(nums):
                res.append(subset[:])
                return

            # include nums[i]
            subset.append(nums[i])
            dfs(i + 1)

            # exclude nums[i]
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res

 

---

Leetcode 78. Subsets

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

 

 

 

 

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

 

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

 

 

 

 

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

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