Combination Sum III

題目描述

找出所有用 K 個 1-9 的數字（不重複使用）使其和為 N 的組合。

輸入：k = 3, n = 7
輸出：[[1,2,4]]
解釋：1+2+4=7，唯一的組合

輸入：k = 3, n = 9
輸出：[[1,2,6],[1,3,5],[2,3,4]]

解題思路

定義搜尋空間

候選數字固定為 1-9，每個最多選一次。搜尋空間是 C(9,k) 種組合

回溯框架

backtrack(remain, start, path)：remain 是剩餘目標和，start 是本層起始數字，path 是當前已選數字

剪枝條件

path 長度已達 k → 檢查 remain 是否為 0；i > remain → break（後面數字更大不可能湊出）

收集結果

path.length == k 且 remain == 0 → 複製 path 加入結果集。兩條件缺一不可

避免重複

遞迴時傳 start = i+1，保證後選數字嚴格大於先選，避免 [1,2,4] 和 [2,1,4] 重複

程式碼

C#

csharp

public class Solution {
    public IList<IList<int>> CombinationSum3(int k, int n) {
        var result = new List<IList<int>>();
        Backtrack(k, n, 1, new List<int>(), result);
        return result;
    }
    
    private void Backtrack(int k, int remain, int start,
                           List<int> path, List<IList<int>> result) {
        if (path.Count == k) {
            if (remain == 0) result.Add(new List<int>(path));
            return; // 不管是否等於 0 都要 return，已經選了 k 個
        }
        for (int i = start; i <= 9; i++) {
            if (i > remain) break; // 剪枝：當前數字已超過剩餘和
            path.Add(i);
            Backtrack(k, remain - i, i + 1, path, result);
            path.RemoveAt(path.Count - 1); // 回溯
        }
    }
}

TypeScript

typescript

function combinationSum3(k: number, n: number): number[][] {
    const result: number[][] = [];
    
    function backtrack(remain: number, start: number, path: number[]) {
        if (path.length === k) {
            if (remain === 0) result.push([...path]);
            return;
        }
        for (let i = start; i <= 9; i++) {
            if (i > remain) break; // 剪枝
            path.push(i);
            backtrack(remain - i, i + 1, path);
            path.pop(); // 回溯
        }
    }
    
    backtrack(n, 1, []);
    return result;
}

Python

python

def combinationSum3(k: int, n: int) -> list[list[int]]:
    result = []
    
    def backtrack(remain: int, start: int, path: list[int]):
        if len(path) == k:
            if remain == 0:
                result.append(path[:])  # 複製一份加入結果
            return
        for i in range(start, 10):
            if i > remain:  # 剪枝：後面的數字更大，不可能湊出
                break
            path.append(i)
            backtrack(remain - i, i + 1, path)
            path.pop()  # 回溯
    
    backtrack(n, 1, [])
    return result

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O(C(9,k)) | O(k) |

C(9,k) 是從 9 個數字中選 k 個的組合數，最多 C(9,4) = 126。

Time：搜尋空間最多 C(9,k) 種組合，加上剪枝實際探索更少。k=4 時最多 126 種，非常快
Space：遞迴深度為 k，path 陣列大小為 k，合計 O(k)

圖解

開始 k=3, n=7

i=1→

選 1, 剩餘 6

i=2→

選 2, 剩餘 4

i=4 → 答案→

選 4, 剩餘 0 ✓

→

選 3, 剩餘 3

剪枝→

下一個 4>3 剪枝

圖表展示了回溯搜尋樹的實際走訪過程：選 1→2→4 時 remain=0 找到答案 [1,2,4]。選 1→3 後剩餘 3，下一個數字 4 > 3，直接 break 剪枝，避免無效搜尋。

進階觀點

💡面試追問

和 Combination Sum 系列的差別？ 39 題允許重複使用同一數字（遞迴傳 i 不是 i+1）；40 題有重複元素需跳過同層相同值；本題數字固定 1-9 且不重複，是最單純的版本。
剪枝用 break 而不是 continue 的原因？ 因為迴圈是 i 從 start 到 9 遞增的。如果 i > remain，那 i+1, i+2... 更大，加上去只會讓 remain 變更負，全都不可能成功，所以直接 break 結束整層。
能再加什麼剪枝？ 檢查「剩餘 k - path.length 個數字能湊出的最大和」是否 ≥ remain。最大和 = 9 + 8 + ... 取最後幾個，如果連最大都不夠就提前 return。

邊界情況

n 大於 45（1+2+...+9=45）：不可能湊出，直接回傳空陣列
k 等於 1：答案就是 n 本身（如果 1 ≤ n ≤ 9），回傳 [[n]]
k 等於 9：只有一種選法 [1,2,...,9]，且 n 必須等於 45 才有解

理解測驗

🤔 為什麼遞迴時下一層從 i+1 開始而不是從 1 開始？

🤔 剪枝 if (i > remain) break 的效果是什麼？