---
title: "78. Subsets"
url: "https://laigary.com/interview/coding/78-subsets"
type: "note"
section: "coding"
date: "2023-01-27"
updated: "2026-07-26"
tags: ["Backtrack", "Classic"]
---

# 78. Subsets

[78\. Subsets](https://leetcode.com/problems/subsets/)

給一個**沒有重複元素**的陣列，回傳所有子集（冪集合）。

## 思路

子集和排列的差別在於**順序不重要**：`[1,2]` 和 `[2,1]` 是同一個子集，只能算一次。

要避免重複，作法是規定「**只能往後選**」—— 每一層都從上一次選的索引之後開始挑，這樣任何一個子集都只會用「索引遞增」的那一種順序被產生出來，天然不重複。這就是 `start` 參數的用途。

| | 每一層可以選什麼 | 用什麼控制 |
|---|---|---|
| **子集 / 組合**（本題） | 只能選**索引比上一個大**的 | `start` 參數 |
| [46. 排列](/interview/coding/46-permutations) | 全部元素，只要**還沒用過** | `visited` 集合 |

第二個關鍵是**什麼時候收集答案**：

> **每進入一個節點就收集一次**，不是只在葉節點收集。

因為回溯樹上的**每一個節點都是一個合法的子集** —— 根節點是空集合、第一層是單元素子集⋯⋯所以 `res.append(list(curr))` 要放在函式的最上面，而且**沒有終止條件**（`for` 迴圈跑完自然就返回了）。

這一點是子集題和其他回溯題最大的不同。[46](/interview/coding/46-permutations) 要等 `len(curr) == len(nums)`、[39](/interview/coding/39-combination-sum) 要等 `target == 0`，只有子集題是「隨走隨收」。

## 解題方向

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

        res = []
        n = len(nums)

        def backtrack(curr, start):
            res.append(list(curr))
            
            for i in range(start, n):
                curr.append(nums[i])
                backtrack(curr, i + 1)
                curr.pop()
        

        backtrack([], 0)
        
        return res
```

三個要點：

- **`res.append(list(curr))` 在最前面** —— 每個節點都是答案，理由見上面
- **`list(curr)` 的複製不能省** —— `curr` 是同一個 list 一路被修改，直接放進去的話最後全部會變成空的
- **遞迴傳的是 `i + 1` 不是 `start + 1`** —— 要從「剛選的這個」的下一個開始，傳 `start + 1` 會讓同一層的不同分支互相干擾

`for i in range(start, n)` 配 `backtrack(curr, i + 1)` 是組合型回溯的固定骨架，見 [Backtracking 模板](/interview/coding/backtracking-template)。

## 補充

**另一種思路：把子集看成二進位。** `n` 個元素的每個子集都對應一個 `n` 位元的 0/1 遮罩（第 `i` 位是 1 代表選了 `nums[i]`），所以枚舉 `0` 到 `2^n - 1` 就枚舉完所有子集了：

```python
        res = []
        for mask in range(1 << len(nums)):
            res.append([nums[i] for i in range(len(nums)) if mask & (1 << i)])
        return res
```

複雜度一樣，但完全不用遞迴。這個「子集 ↔ 位元遮罩」的對應在狀態壓縮 DP 裡很常用，值得知道。

**有重複元素的版本**是 [90. Subsets II](/interview/coding/90-subsets-ii)：先排序，然後在同一層跳過重複值（`if i > start and nums[i] == nums[i-1]: continue`）。注意條件是 `i > start` 不是 `i > 0` —— 只跳過**同一層**的重複，不影響往下遞迴時再次選到相同的值。

**同一個 `start` 骨架的其他題**：[77. Combinations](/interview/coding/77-combinations)（固定長度）、[39. Combination Sum](/interview/coding/39-combination-sum)（可以重複選同一個，所以傳 `i` 而不是 `i + 1`）、[131. Palindrome Partitioning](/interview/coding/131-palindrome-partitioning)。

## 複雜度

- 時間 $O(n \times 2^n)$ — 有 $2^n$ 個子集，每個平均要花 $O(n)$ 複製進結果
- 空間 $O(n)$ — 遞迴深度最多 `n`，`curr` 也是 $O(n)$（不含輸出）

其中 `n` 是元素個數。和 [46. Permutations](/interview/coding/46-permutations) 一樣，**輸出本身就是這個量級，所以沒有更快的解法** —— 被問到「能不能優化」時這就是答案。