216 - Combination Sum III

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:

[[1,2,4]]

Example 2:
Input: k = 3, n = 9
Output:

[[1,2,6], [1,3,5], [2,3,4]]

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Hide Tags
Array Backtracking
Hide Similar Problems
(M) Combination Sum

跟 039 基本类似，穷尽各种组合，只不过范围是 1~9 的数字而已。
另外就是要检查 k 和 n 同时为0，才是所求的答案。

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> rst;
        vector<int> buf;

        if(!k || n<1)
            return rst;

        for(int ii=1; ii<10; ++ii)
        {
            buf.push_back(ii);
            build(k-1, n-ii, ii+1, buf, rst);
            buf.pop_back();
        }
        return rst;
    }
   
    void build(int k, int n, int start, vector<int>& buf, vector<vector<int>>& rst)
    {
        if(!n && !k)
            rst.push_back(buf);
        else
        {
            if(n>=start)
                for(int ii=start; ii<10; ++ii)
                {
                    buf.push_back(ii);
                    build(k-1, n-ii, ii+1, buf, rst);
                    buf.pop_back();
                }
        }
    }
};
0 ms.