題目： LeetCode - 216. Combination Sum III

題目說明

給兩個整數 k 及 n，求在 1 ~ 9 的數字中，找出 k 個相加會等於 n 的數，此為一組，一組內的數字不可重複，每組中的數不可相同。

解題思路

使用 dfs 尋找解，為了避免重複，我們由小找到大，每次遞迴中先判斷 k 及 n，若 k 為 0 代表數字已經夠了，此時若是 n 為 0 則代表這是一組解。接著使用迴圈，i 從 bound 開始到 9 繼續做 dfs。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n)
    {
        vector<vector<int>> res;
        vector<int> cur;
        dfs(k, n, 1, cur, res);
        return res;
    }
private:
    void dfs(int k, int n, int bound, vector<int>& cur, vector<vector<int>>& res)
    {
        if(!k) { if(!n) res.emplace_back(cur); return; }
        for(int i = bound; i <= 9; ++i)
        {
            cur.emplace_back(i);
            dfs(k - 1, n - i, i + 1, cur, res);
            cur.pop_back();
        }
    }
};