216. Combination Sum III - cocoder39/coco39_LC GitHub Wiki

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        self.helper(1, n, k, [], res)
        return res
        
    def helper(self, cur, target, k, path, res):
        if target == 0 and len(path) == k:
            res.append(path[:])
            return
        
        if target < 0 or len(path) >= k:
            return
        
        for i in range(cur, 10):
            path.append(i)
            self.helper(i+1, target-i, k, path, res)
            path.pop()

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> res;
        vector<int> cur;
        helper(res, cur, n, k, 1);
        return res;
    }
private:
    void helper(vector<vector<int>>& res, vector<int>& cur, int n, int k, int start) {
        if (n == 0 && k == 0) {
            res.push_back(cur);
            return;                                    //min           max
        } else if (n < 0 || k < 0 || start >= 10 || n < start || n > k * 9) {
            return;
        }
        
        for (int i = start; i <= 9; i++) {
            cur.push_back(i);
            helper(res, cur, n - i, k - 1, i + 1);
            cur.pop_back();
        }
    }