嘻嘻嘻

    image.png
    首先我们看一下这道题和39题，40题的区别
    这道题说的是从1-9里面挑选k个数，和为n
    也就是在40题的基础上加了一个条件k个数，数组则变成了[1,2,3,4,5,6,7,8,9]

    1. class Solution {
    2.    vector<vector<int>> res;
    3.    vector<int> v;
    4.    int k;
    5.    void dfs(int remain, int start)
    6.    {
    7.        if(v.size() == k)
    8.        {
    9.            if(remain == 0)
    10.                res.push_back(v);
    11.            return;
    12.        }
    13.        if(remain < 0 || start > 9)
    14.        {
    15.            return;
    16.        }
    17.        for(int i = start; i <= 9; i++)
    18.        {
    19.            v.push_back(i);
    20.            dfs(remain - i, i + 1);
    21.            v.pop_back();
    22.        }
    23.    }
    24. public:
    25.    vector<vector<int>> combinationSum3(int _k, int n) {
    26.        k = _k;
    27.        int sum = (1 + 9) * 9 / 2;
    28.        if(k > 9 || n > sum) return res;//如果大于9个数说明是不可能的；9个数字总和也不能大于45
    29.        dfs(n, 1);
    30.        return res;
    31.    }
    32. };

    第二次写题

    class Solution {
    vector<vector<int>> res;
    vector<int> path;
    int iTarget;
    int k;
    void dfs(int iSum, int iCur)
    {
        if(iSum > iTarget || path.size() > k) return;
        if(iSum == iTarget)
        {
            if(path.size() == k)
            {
                res.push_back(path);
                return;
            }
        }
        if(iCur > 9) return;
        if(iSum + iCur > iTarget) return;
        //不加入
        dfs(iSum, iCur + 1);
        //加入
        path.push_back(iCur);
        dfs(iSum + iCur, iCur + 1);
        path.pop_back();
    }
public:
    vector<vector<int>> combinationSum3(int _k, int n) {
        if(n > 45) return res;
        k = _k;
        iTarget = n;
        dfs(0, 1);
        return res;
    }
};