【Leetcode 筆記】78. Subsets

題目解釋

給定一個由 distinct 元素組成的整數 array nums，傳回所有可能的元素 subsets。
解決方案集不得包含重複的子集，您可以 以任何順序回傳組合。

範例

• 輸入: nums = [1, 2, 3]
• 輸出: [[],[1],[2],[1, 2],[3],[1, 3],[2, 3],[1, 2, 3]]

最佳解法

經典的排列組合題，這邊借用 Neetcode 畫的圖，原始解說連結 點此。

假設我們有一個 list subsets，我們每次都可以決定要不要加元素進去，
root 的左邊是選擇加入元素，而 root 的右邊是選擇不加入元素。

而我們把做決策的步驟畫成一棵樹，
因此最左方的 child 是放滿元素的狀態，最右方是什麼都不放。

因為 subsets 裡面的元素會不斷被抽換掉，
所以我們每次遞迴都要把新狀態給加入最後要 return 的 results 裡面。

程式碼

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

        def _dfs(i):
            if i >= len(nums):
                results.append(subsets.copy())
                return
            else:
                # add element, left leaf
                subsets.append(nums[i])
                _dfs(i + 1)

                # remove element, right leaf
                subsets.pop()
                _dfs(i + 1)

        _dfs(0)
        return results

時間複雜度

O(n * 2^n)，n 是 nums 的長度。

2^n 是 subsets 的總數，對於每個 subset，
我們可能需要 O(n) 的時間來複製並把它加到結果集中。

空間複雜度

O(n)，n 是 nums 的長度。

結語

高頻題，務必好好把握❗

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26