陳憲億 Joseph Chen | Software Engineer & AI Developer

Joseph Chen

2026

12 min read

3 題精講

學完 Graph 的拓撲排序，下一個大主題是 Backtracking（回溯）。這類題目的特徵很明顯：「列出所有可能的組合 / 排列 / 子集」。

Backtracking 的核心思想其實很像人做選擇：往前走一步，看看這條路能不能通；不行的話，退回來（backtrack），換下一個選擇再試。這個「退回來」的動作，在程式裡就是 path.pop()。

這篇用三道題把這個框架從頭到尾打通。

Backtracking 通用框架

先把框架背起來，後面所有題目都是這個框架的變形：

backtracking_template.py

def backtrack(start, path):
    # 1. 收集結果（什麼時候把 path 加入 result？）
    result.append(path[:])   # 注意：要複製，不是傳引用

    # 2. 枚舉選擇
    for i in range(start, len(nums)):
        # 3. 做選擇
        path.append(nums[i])

        # 4. 遞迴（進入下一層）
        backtrack(i + 1, path)

        # 5. 撤銷選擇（關鍵！）
        path.pop()

框架三個核心問題

Q: 什麼時候收集結果？

A: 每進入一層就收集（Subsets）、只在特定條件下收集（Combination Sum 加到 target）、到葉節點收集（Permutations）

Q: 枚舉什麼？

A: 從 start 開始枚舉，避免重複選取之前的元素（組合題）；或枚舉所有未選過的元素（排列題）

Q: 如何剪枝？

A: 加總超過 target 就不繼續（Combination Sum）；遇到重複元素就跳過（有重複的 Subsets/Permutations 變形）

🌿

Part 1 — Subsets

#78 · Medium · 列出所有子集

題目

給一個不含重複元素的整數陣列 nums，返回所有可能的子集（冪集）。結果不能有重複的子集。

Input: nums = [1, 2, 3]

Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

思路：每一層都是一個答案

Subsets 和一般 backtracking 最大的不同是：每進入一層遞迴，當下的 path 就是一個合法的子集。不用等到葉節點才收集，一進函式就收集。

nums = [1, 2, 3] 的遞迴樹

[] ✓

[1] ✓

[2] ✓

[3] ✓

[1,2] ✓

[1,3] ✓

[2,3] ✓

[1,2,3] ✓

每個節點進入時立刻收集 → 共 2³ = 8 個子集（空集合 + 7 個）

subsets.py

def subsets(nums: list[int]) -> list[list[int]]:
    result = []

    def backtrack(start, path):
        result.append(path[:])   # 每一層都收集（不管 path 是不是空的）

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)   # i+1：不往回選，只選後面的元素
            path.pop()               # 撤銷選擇

    backtrack(0, [])
    return result

# Output for [1, 2, 3]:
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

⏱ Time: O(n × 2ⁿ)💾 Space: O(n)

為什麼 Time 是 O(n × 2ⁿ)？

n 個元素的子集共有 2ⁿ 個。每個子集最多有 n 個元素需要複製（path[:]），所以總時間是 O(n × 2ⁿ)。Space O(n) 是遞迴深度（不計結果本身）。

🔀

Part 2 — Permutations

#46 · Medium · 全排列

題目

給一個不含重複數字的陣列 nums，返回所有可能的全排列。

Input: nums = [1, 2, 3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Subsets vs Permutations 的差異

	Subsets（組合）	Permutations（排列）
順序重要嗎？	❌ [1,2] 和 [2,1] 是同一個	✅ [1,2] 和 [2,1] 不同
如何避免重複？	傳 `start`，只選後面的元素	用 `used` 集合，標記已選元素
何時收集結果？	每一層都收集	path 長度等於 nums 長度時
答案數量	2ⁿ 個	n! 個

permutations.py

def permute(nums: list[int]) -> list[list[int]]:
    result = []

    def backtrack(path, used):
        # 收集條件：path 已選滿所有元素
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if i in used:        # 這個元素已經在 path 裡了，跳過
                continue

            used.add(i)
            path.append(nums[i])
            backtrack(path, used)
            path.pop()           # 撤銷
            used.remove(i)       # 撤銷

    backtrack([], set())
    return result

⏱ Time: O(n × n!)💾 Space: O(n)

nums = [1, 2, 3]，以選 1 開頭為例

start: []

path=[1]

used={0}

path=[1,2]

used={0,1}

path=[1,2,3] ✓

path=[1,3]

used={0,2}

path=[1,3,2] ✓

以此類推，以 2、3 開頭各有 2 條路 → 共 3! = 6 個排列

💡 用 set 還是 boolean array？

上面用 set() 儲存已用的 index。另一種常見寫法是用 used = [False] * len(nums)，效能稍好（O(1) 查詢 vs 平均 O(1) 但 worst case 略差）。面試時兩種都可以，但 boolean array 更直觀。

🎯

Part 3 — Combination Sum

#39 · Medium · 湊到 target 的所有組合

題目

給一個不含重複元素的正整數陣列 candidates 和目標數 target。找出所有加總等於 target 的組合，每個元素可以重複使用。

Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3], [7]]

兩個關鍵點

1. 元素可以重複使用

遞迴時傳的是 i 而不是 i+1，允許在同一層繼續選同一個元素。

backtrack(i, path) # 可以再選 i

2. 剪枝：超過 target 就停

如果目前加總已經超過 target，這條路不可能成功，直接 return。先排序 candidates 可以讓剪枝更早發生。

if remain < 0: return # 剪枝

combination_sum.py

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    result = []
    candidates.sort()   # 排序後可以更早剪枝

    def backtrack(start, path, remain):
        if remain == 0:              # 剛好湊到 target
            result.append(path[:])
            return
        if remain < 0:               # 超過了，剪枝
            return

        for i in range(start, len(candidates)):
            # 小優化：candidates 已排序，若當前元素就超了，後面更不用看
            if candidates[i] > remain:
                break

            path.append(candidates[i])
            backtrack(i, path, remain - candidates[i])  # 注意：傳 i，不是 i+1
            path.pop()

    backtrack(0, [], target)
    return result

# candidates = [2,3,6,7], target = 7
# 路徑：2 → 2 → 2 → 2 (remain=-1, 剪枝)
#                 → 3 (remain=0, 收集 [2,2,3] ✓)
#             → 3 → (remain=0? 2+2+3... 不對，繼續)
#        → 3 → ...
#        → 6 → ...
#        → 7 → (remain=0, 收集 [7] ✓)

⏱ Time: O(n^(T/M))💾 Space: O(T/M)

複雜度說明

T 是 target，M 是最小的 candidate。最壞情況下遞迴樹深度是 T/M，每層最多有 n 個選擇，所以是 O(n^(T/M))。空間是遞迴深度 O(T/M)。

candidates=[2,3,6,7], target=7 部分遞迴樹

remain=7

pick 2, remain=5

pick 2, remain=3

pick 2, remain=1

pick 2, remain=-1 ✂️ 剪枝

pick 3, remain=-2 ✂️ 剪枝

pick 3, remain=0 → [2,2,3] ✓

... 其他分支

pick 7, remain=0 → [7] ✓

三題統一對比

題目	何時收集	避免重複	遞迴參數	剪枝
#78 Subsets	每進一層	傳 start，往後選	backtrack(i+1, path)	無
#46 Permutations	path 填滿時	used set 標記	backtrack(path, used)	used 檢查
#39 Combination Sum	remain == 0	傳 start，往後選	backtrack(i, path, remain)	remain < 0 return

識別 Backtracking 題目的訊號

→「列出所有...」「找出所有可能的...」「返回所有組合...」
→輸入是陣列或字串，輸出是「list of list」
→暴力做法是多層 for loop，但層數不固定
→問題可以用「選或不選」這個決策樹來建模

常見陷阱

❌ 忘記複製 path

wrong_way.py

# 錯誤：直接 append path（引用）
result.append(path)    # path 之後被 pop 修改，result 裡的也會變！

# 正確：append 複製
result.append(path[:])
result.append(list(path))  # 這兩種都可以

這是 backtracking 最常見的 bug。path 是可變物件，直接 append 只是存了引用，之後 pop 操作會同步影響 result 裡的值。

⚠️ Combination Sum：傳 i 而非 i+1

combination_sum_key.py

# Subsets 和一般組合題：傳 i+1（不允許重複使用同元素）
backtrack(i + 1, path)

# Combination Sum：傳 i（允許重複使用同元素）
backtrack(i, path, remain - candidates[i])

這個細節決定「元素能不能重複選」，是這題和 Subsets 最大的不同。

這篇學到什麼

🌿Backtracking 本質是枚舉 + 撤銷：做選擇 → 遞迴 → 撤銷，三個動作缺一不可

📋Subsets：每層都收集；Permutations：用 used 標記，長度填滿才收集；Combination Sum：remain==0 才收集

🔀組合題傳 start（不回頭選），排列題傳 used（全範圍但跳過已選），這是避免重複的核心差異

✂️剪枝讓效率大幅提升：Combination Sum 先排序，remain < 0 直接 return，candidates[i] > remain 直接 break

⚠️永遠記得 result.append(path[:])，直接 append path 是 backtracking 最常見的 bug

EP.14 — Graph 拓撲排序

Course Schedule、Kahn's Algorithm

EP.16 — Greedy

Jump Game、Gas Station

LeetCode

Backtracking

Subsets

Permutations

Combination Sum

Python

EP.15

EP.15 — Backtracking：走不通就退回來