# [LeetCode] 216. Combination Sum III 组合之和 III

2021年09月15日 阅读数：1

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.html

Example 1:java

Input: k = 3, n = 7python

Output:app

`[[1,2,4]]`

Example 2:post

Input: k = 3, n = 9this

Output:url

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.code

Java:blog

```class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
List<Integer> curr = new ArrayList<Integer>();
helper(result, curr, k, 1, n);
return result;
}

public void helper(List<List<Integer>> result, List<Integer> curr, int k, int start, int sum){
if(sum<0){
return;
}

if(sum==0 && curr.size()==k){
return;
}

for(int i=start; i<=9; i++){
helper(result, curr, k, i+1, sum-i);
curr.remove(curr.size()-1);
}
}
}
```

Python:

```class Solution:
# @param {integer} k
# @param {integer} n
# @return {integer[][]}
def combinationSum3(self, k, n):
result = []
self.combinationSumRecu(result, [], 1, k, n)
return result

def combinationSumRecu(self, result, intermediate, start, k, target):
if k == 0 and target == 0:
result.append(list(intermediate))
elif k < 0:
return
while start < 10 and start * k + k * (k - 1) / 2 <= target:
intermediate.append(start)
self.combinationSumRecu(result, intermediate, start + 1, k - 1, target - start)
intermediate.pop()
start += 1　　```

C++:

```class Solution {
public:
vector<vector<int> > combinationSum3(int k, int n) {
vector<vector<int> > res;
vector<int> out;
combinationSum3DFS(k, n, 1, out, res);
return res;
}
void combinationSum3DFS(int k, int n, int level, vector<int> &out, vector<vector<int> > &res) {
if (n < 0) return;
if (n == 0 && out.size() == k) res.push_back(out);
for (int i = level; i <= 9; ++i) {
out.push_back(i);
combinationSum3DFS(k, n - i, i + 1, out, res);
out.pop_back();
}
}
};```

[LeetCode] 77. Combinations 全组合

[LeetCode] 39. Combination Sum 组合之和

[LeetCode] 40. Combination Sum II

[LeetCode] 216. Combination Sum III

[LeetCode] 377. Combination Sum IV