216. 组合总和 III

Problem: 216. 组合总和 III

思路

与题目组合相识,用回溯算法暴力搜索,但是此题限定的1-9,并且不能重复。

此题中要注意：backTracing(k,n,i + 1);不要写错了，一开始我写成了backTracing(k,n,startIndex + 1);

并且我们可以进行减枝，if(sum > n) return;

回溯真的是一个美妙的过程，无论成功与否都可以回溯，要是人人生也如此就好了。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {
public:
    vector<int> path;
    int sum;
    vector<vector<int>> res;
    void backTracing(int k,int n,int startIndex) {
        if(sum > n) return;
        if(path.size() == k) {
            if(sum == n) {
                res.push_back(path);
                return;
            } else {
                return;
            }
        }
        for(int i = startIndex; i <= 9; i++) {
            path.push_back(i);
            sum += i;
            backTracing(k,n,i + 1);
            path.pop_back();
            sum -= i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backTracing(k,n,1);
        return res;
    }
};