216. Combination Sum III

題目網址：https://leetcode.cn/problems/combination-sum-iii/

題意：找出所有相加之和為 n 的 k 個數的組合，且滿足下列條件：

• 只使用數字 1 到 9
• 每个數字最多使用一次

以任意順序返回所有可能的組合, 組合不能重複。

Solution：

想法：利用 DFS + Backtracking

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n, 1);
        return res;
    }

private:
    vector<int> cur;
    vector<vector<int>> res;

    void dfs(const int k, const int n, const int i){
        if (k == 0 && n == 0) {
            res.emplace_back(cur);
            return;
        }

        for (int j = i; j <= 9; ++j) {
            if (j > n) { // 剪枝
                return;
            }

            // 取 j
            cur.emplace_back(j);
            dfs(k - 1, n - j, j + 1);
            cur.pop_back();
        }
    }
};

• time：$O(k \cdot \binom{M}{k})$ ➔ 其中 M 為集合的大小，本題中 M 固定為 9
  • 共 $\binom{M}{k}$ 種組合, 每建一種需判斷 k 次
• space：$O(k)$ ➔ $O(k) + O(k)$
  • $O(k)$：cur 最大長度為 k
  • $O(k)$：遞迴最大深度為 k