1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    vector<vector<int>> result;
    vector<int> list;

    void search(int now, int k, int n, int sum) {
        if (list.size() == k && sum == n) {
            result.push_back(list);
        }
        if (list.size() >= k || now > 9) {
            return;
        }
        list.push_back(now);
        search(now + 1, k , n , sum + now);
        list.pop_back();
        search(now + 1, k , n , sum);
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear();     
        list.clear();

        search(1, k, n, 0);

        return result;
    }
};