组合总和3

题目

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

思路

和组合一样的方法，只需加一个判断即可

class Solution {
public:
    vector<vector<int>> res;
    void combineAux(vector<int>& tmp, int n, int k, int sum)
    {
        for(int i=n;i>=k;--i)
        {
            tmp[k-1] = i;
            if(k-1 == 0)
            {
                if(accumulate(tmp.begin(), tmp.end(), 0) == sum)
                {
                    res.emplace_back(tmp);
                }
                continue;
            }
            combineAux(tmp, i-1, k-1, sum);
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> vec(k);
        combineAux(vec, 9, k, n);
        return res;
    }
};

改变sum的值，从而不需要累加

class Solution {
public:
    vector<vector<int>> res;
    void combineAux(vector<int>& tmp, int n, int k, int sum)
    {
        for(int i=n;i>=k;sum += i, --i)
        {
            tmp[k-1] = i; sum -= i;
            if(k-1 == 0)
            {
                if(sum == 0) res.emplace_back(tmp);
                continue;
            }
            combineAux(tmp, i-1, k-1, sum);
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> vec(k);
        combineAux(vec, 9, k, n);
        return res;
    }
};