leetcode_combination_sum_iii

发表于

难度：Medium

使用回溯法，递归调用。

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
28
29
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ret;
        vector<int> cur_vec;
        combination_sum_3_recur(ret,k,n,cur_vec);
        return ret;
    }
    
    void combination_sum_3_recur(vector<vector<int>> &ret, int k, int rest, vector<int> &cur_vec)
    {
        if(k == 0 && rest == 0)
        {
            ret.push_back(cur_vec);
            // for_each(cur_vec.begin(), cur_vec.end(),[](int i){cout<<i<<" ";});
            // cout<<endl;
        }
        else if(k > 0 && rest > 0)
        {
            int start = (cur_vec.empty() ? 1 : cur_vec.back()+1);
            for(int i = start; i <= 9; i++)
            {
                cur_vec.push_back(i);
                combination_sum_3_recur(ret,k-1,rest-i,cur_vec);
                cur_vec.pop_back();
            }
        }
    }
};

0ms，超过42.38%