216.组合总数3

题目描述：

由于循环层数是不确定的，考虑递归的方法来做，每一层都更新余下数字和、余下数字个数、起始数字，都要保留两个储存结果的数组。

递归中利用回溯的思想，每次push_back后必须跟随pop_back，如果其他数字发生改变，也需要在递归调用后改回来。

由于递归的终点是输出一个结果，不需要判断真假，函数返回值void即可。

代码

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ret;
        vector<int> temp;
        int sum = n;
        int head = 1;
        dfs(sum, head, k, ret, temp);
        return ret;
    }

    void dfs(int sum, int head, int k, vector<vector<int>>& ret, vector<int>& temp)
    {
        if(k == 1)
        {
            if(sum >= head && sum < 10)
            {
                temp.push_back(sum);
                ret.push_back(temp);
                temp.pop_back();
            }
            return;
        }
        for(int i = head; i + k < 11 && i < 9; i++)//这里可以剪枝
        {
            temp.push_back(i);
            dfs(sum - i, i + 1, k-1, ret, temp);//这样写可以免除sum  i  k  ret的还原
            temp.pop_back();
        }
        return;//可以不写return
    }
    
};