【Leetcode】python - [78] Subsets 個人解法筆記 #重要題型

題目出處

難度

Medium

題目分類

Array, Backtracking, Bit Manipulation

2026-10-09 三刷

個人範例程式碼 - 三刷 (2026/10/09)

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        ans = []
        end = len(nums)
        def dfs(start, path):
            if start == end:
                ans.append(path[:])
                return

            # no pick
            dfs(start+1, path)

            # pick (backtracking)
            path.append(nums[start])
            dfs(start+1, path)
            path.pop()

        dfs(0, [])
        return ans

算法說明

組合問題 (與 LC 77 題是兄弟)，可以對照參考。
簡單來說就是要做出 backtracking, append 與 pop 交替使用。

Time Complexity

O(n*2^n)

# 2^n：選或不選
# n: (小心，經常忘記) 複製的時間成本是 O(n)

Space Complexity

O(n) # 遞迴最大深度

2026-09-30 二刷

個人範例程式碼 - 二刷 (2026/09/30)

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        ans = []
        path = []

        def dfs(i):
            if i == len(nums):
                ans.append(path[:])
                return

            dfs(i+1) # not pick
            path.append(nums[i])
            dfs(i+1) # pick
            path.pop()

        dfs(0)
        return ans

算法說明

注意：這題經常會跟 LeetCode 77 (LC 77 Combinations 筆記) 搞混在一起，主要差別是結束條件不同
這題是所有子集 (2^n)，LC 77 是所有組合 C(n, k) 不太一樣，但寫法很容易搞混。

主要就是透過 DFS，並在每一輪都有決定「選 or 不選」，組出所有的可能性。

Time Complexity

O(n*2^n)

2^n：所有的選與不選
n：複製 path 需要 n 的時間

Space Complexity

O(n)

主要是遞回深度，最多 n 層 (所有數字)

2022-05-23 一刷

個人範例程式碼 - 一刷 (2022/05/23)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]

        ans = []
        self.dfs(nums, 0, [], ans)

        # print(ans)        
        return ans

        # [] 
        # [1] [12] [123]
        #     [13]
        # [2] [23]
        # [3]

    def dfs(self, nums, start, combination, ans):

        ans.append(combination[:]) # deepcopy

        # end of recursion        
        # define and split (use or not use)
        for i in range(start, len(nums)):       
            combination.append(nums[i])
            self.dfs(nums, i+1, combination, ans)
            combination.pop() # backtracking

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

經典 DFS 的組合問題，思考方式如下：

每一層我們都可以決定「取特定數字或不取」，但取或不取，順序都要一直往後。

【Leetcode】python - [78] Subsets 個人解法筆記 #重要題型

input handling

如果沒有 nums，return [[]]

Boundary conditions

用 dfs 內的 for loop 控制搜尋範圍

Reference

子集 · Subsets