[Leetcode] 78. Subsets

문제 바로가기

각 반복에서 지금까지 생성된 subset에 현재 숫자를 추가한 subset을 생성하고 추가한다.
즉, 현재 숫자가 k일 때 누적된 k-1까지의 subset은 $2^{k-1}$개이므로 k를 포함하는 $2^{k-1}$개의 새로운 subset 추가 작업을 수행한다. 따라서 총 연산의 수는 $\sum_{k=1}^{n}2^{k-1}$이 된다.

Time Complexity: $O(2^n)$
Space Complexity: $O(2^n)$

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for num in nums:
            length = len(res)
            for i in range(length):
                res.append(res[i] + [num])
        
        return res