leetcode 打卡，216 组合总和3

相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，不得重复使用。

那就从1开始考虑取或者不取，不取就看后面是否取2,3,4……，取了就在后面对应的结果(当然总共取k个数，那后面就只能取k-1个)里添加本数。

写了两种方法，一开始的多一重循环，后来去掉了，不过意外的是多一重循环的那个反而更快。

class Solution {
public:
    vector> combinationSum3(int k, int n) {
        return combinationSum3(k,n,1);
    }
    vector> combinationSum3(int k, int n,int c) {
        if(c>n)return {};
        if(c>9)return {};
        if(k==1){
            if(n<10)return {{n}};
            return {};
        }
        vector> ans;
        int b=min(10,n);
        for(int i=c;i>temp=combinationSum3(k-1,n-i,i+1);
            for(auto &item:temp){
                item.push_back(i);
                ans.push_back(item);
            }
        }
        return ans;
    }
};

class Solution {
public:
    vector> combinationSum3(int k, int n) {
        return combinationSum3(k,n,1);
    }
    vector> combinationSum3(int k, int n,int c) {
        if(c>n)return {};
        if(c>9)return {};
        if(k==1){
            if(n<10)return {{n}};
            return {};
        }
        vector>ans=combinationSum3(k,n,c+1);
        vector>temp=combinationSum3(k-1,n-c,c+1);
        for(auto &item:temp){
            item.push_back(c);
            ans.push_back(item);
        }
        return ans;
    }
};