LeetCode 216：組合總和 III——DFS 回溯尋找 k 個數之和為 n

題目描述

從 1 到 9 中選出 k 個互不相同的數字，使其和等於 n。返回所有可能的組合，組合內數字遞增，組合間無序。

回溯策略

• 遞歸參數：當前組合 path、當前和 sum、剩餘可選數字起始值 start、剩餘需選數字數 k。
• 剪枝條件：sum > n 或 k < 0 直接返回；sum == n && k == 0 記錄答案。
• 遍歷 i 從 start 到 9，選擇 i 後遞歸 start = i+1 保證不重複且遞增。

Java 參考實現

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(res, new ArrayList<>(), 0, k, n, 1);
        return res;
    }
    void dfs(List<List<Integer>> res, List<Integer> path, int sum, int k, int n, int start) {
        if (sum == n && k == 0) { res.add(new ArrayList<>(path)); return; }
        if (sum > n || k < 0) return;
        for (int i = start; i <= 9; ++i) {
            path.add(i);
            dfs(res, path, sum + i, k - 1, n, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

複雜度分析

• 時間：最坜 O(C(9, k))，實際受 n 剪枝大幅縮減。
• 空間：遞歸棧 O(k)，結果空間不計入。

總結

經典組合型回溯：有序選擇避免重複，目標和與剩餘個數雙重剪枝。掌握此模板可解決大多數「從無序集合選 k 個滿足條件」的問題。