LeetCode 216 組合總和 III：DFS 回溯 + 剪枝優化

問題描述

找出所有相加之和為 n 的 k 個數的組合。組合中只允許含 1-9 的正整數，且每組合中數字不重複。返回所有可能的組合列表。

核心算法：DFS 回溯 + 剪枝

從 1 到 9 遞歸嘗試選擇數字，維護：

• cur：當前選擇的最後一個數字（保證遞增，避免重複組合）。
• left：剩餘需要的和。
• num：剩餘需要選擇的數字個數。

剪枝條件（關鍵優化）

在遞歸前檢查：

• i > cur：保證遞增選擇。
• left >= i：剩餘和至少要能容納當前數。
• left >= num：剩餘和至少要能容納 num 個最小可用數（即 1+2+... 但這裡簡化為 num，因最小數≥1）。
• left <= num * 9：剩餘和不超過 num 個最大可用數（9）之和。

這四個條件極大縮小了搜索空間。

完整代碼 (C++)

class Solution {
    vector> ans;
    vector path;
public:
    void dfs(int num, int left, int cur) {
        if (num == 0 && left == 0) {
            ans.push_back(path);
            return;
        }
        for (int i = cur + 1; i <= 9; ++i) { // 從 cur+1 開始保證遞增
            if (left >= i && left >= num && left <= num * 9) {
                path.push_back(i);
                dfs(num - 1, left - i, i);
                path.pop_back();
            }
        }
    }
    vector> combinationSum3(int k, int n) {
        dfs(k, n, 0);
        return ans;
    }
};

複雜度分析

• 時間：最坏 O(C(9,k)) = O(1)，因搜索空間固定（9 個數選 k 個），剪枝後極快（題目測試案例僅 18 組，0ms 通過）。
• 空間：O(k) 遞歸棧 + O(C(9,k)*k) 存結果。

關鍵點總結

• 遞增選擇：for (i = cur+1; ...) 保證組合唯一、無重複。
• 剪枝四連擊：left >= i && left >= num && left <= num*9 是本題 AC 關鍵。
• 回溯模板：選擇 → 遞歸 → 撤銷選擇。

總結

LeetCode 216 是組合型回溯的標準練習。掌握「遞增選擇去重 + 和與個數雙重剪枝」模板，可輕鬆解決「組合總和 I/II/III/IV」全系列問題。