LeetCode 筆記 - 78. Subsets

Posted on

題目在此 78. Subsets

給定一個數列，請產生出所有可能的子數列

解題思維

首先以一個 empty list 開始
當走訪到一個新數字時，就把這個新數字加到過去所有結果後面即可

複雜度分析

由於每多一個新數字 O(N)，結果就會變成原來的兩倍 O(2N)

所以最終的 time complexity 為 O(N * 2N)

程式碼

1
2
3
4
5
6
7
8
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        result = [[]]
        
        for num in nums:
            result += [curr + [num] for curr in result]
        return result

也許你也會想看看