[알고리즘, Python] 멱집합 (power set) / 부분집합 구하기

Q. 집합(set)의 모든 부분 집합(subset)들로 구성된 집합(power set)을 구하라 

출처 : Cracking the Coding Interview - Q8.4

 

먼저 하나하나 적어보자.

P([1]) =  [[], [1]]

P([1,2]) = [[], [1], [2], [1,2]]

P([1,2,3]) = [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

 

자세히 살펴보면 P(n)은 P(n-1)에 집합의 마지막 값을 하나 더 넣어준 것과 같다.

 

내 Python 코드

def subsets(nums: List[int]) -> List[List[int]]:

    subset = [[]]
        
    for num in nums:
        prevLength = len(subset)
        for i in range(prevLength):
            ss = subset[i][:]
            ss.append(num)
            subset.append(ss)

    return subset

- Time complexity: O(n * 2^n)

- Space complexity: O(n * 2^n)

 

 

Leetcode 테스트 결과

 

 

Leetcode에서 이 문제 풀어보기