# 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);
return;
}

for(int i=start; i<10; i++){
if (comb.size() < k) {
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;
}
```