216.排列组合 III

题目

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路

别无他长，用暴力吧。
从1-9进行遍历，每次遍历从当前遍历到的元素的下一个开始，然后k-1，n-i传入到下次遍历之中。当k=1并且n比当前遍历的元素大而且比9小的时候，返回这个vector>。
上层遍历拿到返回的vector>之后，把本层遍历的元素放到首位，然然后加入到自己的结果队列之中。

代码

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        return getsum(1,k,n);
    }
    vector<vector<int>> getsum(int s,int k,int n){
        if(k<=0||k>n||s>n) return {};
        if(n>=s&&k==1&&n<=9) return {{n}};
        vector<vector<int>> v;
        for(int i=s;i<=9;i++){
            vector<vector<int>> temp=getsum(i+1,k-1,n-i);
            for(vector<int> t:temp){
                t.insert(t.begin(),i);
                v.push_back(t);
            }
        }
        return v;
    }
};