LeetCode 筆記 - 78. Subsets

Posted on

題目在此 78. Subsets

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

解題思維

迭代法

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

由於每多一個新數字 O(N)，結果就會變成原來的兩倍 $O(N * 2^N)$
所以最終的 time complexity 為 $O(N * 2^N)$

程式碼

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

位元運算

本宅在這裡提供另一種解法，是利用位元運算來解決這個問題。
因為每個數字有兩種狀態：要或不要，所以對於一個有 n 個元素的集合，總共有 $2^n$ 種子集組合。

我們可以使用一個整數來表示每一種組合，這個整數的二進位表示法中的每一位對應到集合中的一個元素：

如果某一位是 1，表示我們選擇了對應的元素；
如果是 0，表示我們沒有選擇該元素。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

        # step 0: using bit to mark which element is picked.
        # step 1: generate 2^n (n = len(nums)), 0 ~ 2^n - 1
        # step 2: for n in range(2^n): if i bit is 1, mean nums[i] is selected.

        # time complexity: O(n * 2^n)
        # space complexity: O(n * 2^n)

        result = []

        size = len(nums)
        n = 2 ** size

        for cur_n in range(n):
            bit = 1

            cur_r = []

            for i in range(size):
                if cur_n & bit != 0:
                    cur_r.append(nums[i])

                bit = bit << 1

            result.append(cur_r)

        return result

也許你也會想看看