Leetcode Combination Sum III problem solution

In this Leetcode Combination Sum III problem solution Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

1. Only numbers 1 through 9 are used.
2. Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Problem solution in Python.

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
         return [list for list in itertools.combinations(range(1, 10), k) if sum(list) == n]

Problem solution in Java.

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> comb = new ArrayList<Integer>();
        List<List<Integer>> op = new ArrayList<List<Integer>>();
        
        helper(op, comb, k, 1, n);
        
        return op;
    }
    
    public static void helper(List<List<Integer>> op, List<Integer> comb, int k, int start, int n){
        if(comb.size() == k && n == 0){
            List<Integer> li = new ArrayList<Integer>(comb);
            op.add(li);
            return;
        }
        
        for(int i=start; i<10; i++){
            if (comb.size() < k) {
                comb.add(i);
                helper(op, comb, k, i+1, n-i);
                comb.remove(comb.size() - 1);
            }
        }
    }
}

Problem solution in C++.

class Solution {
public:
void dfs(vector<vector<int>>& res, vector<int> &pre, int start, int k, int n){
    if (k==0 && n==0){
            res.push_back(pre); return;
    }
    if (start>9 || start>n || k==0) return;
    pre.push_back(start);
    dfs(res,pre,start+1,k-1,n-start);
    pre.pop_back();
    dfs(res,pre,start+1,k,n);
}
vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> res;
    vector<int> pre;
    dfs(res,pre,1,k,n);
    return res;
}
};

Problem solution in C.

void dfs(int **ret,int *candidate,int *rindex,int *cindex,int k,int n,int index){
    if(n==0 && k==0){
        ret[*rindex] = (int*)malloc(sizeof(int)*(*cindex));
        for(int i=0;i<(*cindex);i++){
            ret[*rindex][i]=candidate[i];
        }
        (*rindex)++;
        int **tmp = (int **)realloc(ret,sizeof(int*)*((*rindex)+1));
        if(tmp != NULL){
            ret=tmp;
        }
        return;
    }
    if(index>9 || n<=0 || k<=0){
        return;
    }
    for(int i=index;i<=9;i++){
        if(i>n){
            break;
        }
        *(candidate+(*cindex))=i;
        (*cindex)++;
        dfs(ret,candidate,rindex,cindex,k-1,n-i,i+1);
        (*cindex)--;
    }
}
  
int** combinationSum3(int k, int n, int** columnSizes, int* returnSize) {
    int *candidate = (int*)malloc(sizeof(int)*k);
    memset(candidate,0,sizeof(candidate));
    int **ret = (int **)malloc(sizeof(int*));
    int rindex=0;
    int cindex=0;
    dfs(ret,candidate,&rindex,&cindex,k,n,1);
    *columnSizes = (int *)malloc(sizeof(int)*(rindex));
    for(int i=0;i<rindex;i++){
        (*columnSizes)[i]=k;
    }
    *returnSize=rindex;
    free(candidate);
    return ret;
}