## Algorithm

Problem Name: 216. Combination Sum III

Find all valid combinations of `k` numbers that sum up to `n` such that the following conditions are true:

• Only numbers `1` through `9` are used.
• 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.

Example 1:

```Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.```

Example 2:

```Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
```

Example 3:

```Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.
```

Constraints:

• `2 <= k <= 9`
• `1 <= n <= 60`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <vector>

using namespace std;

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

combinationSum3Helper(1, n, k, temp, ans);

return ans;
}

void combinationSum3Helper(int start, int n, int k, vector<int> &temp, vector < vector<int> > &ans) {
if (k == temp.size() && n == 0) {
ans.push_back(temp);
return;
}
else if (temp.size() > k || n  <  0) {
return;
}

for (int i = start; i  < = 9; i++) {
temp.push_back(i);
combinationSum3Helper(i + 1, n - i, k, temp, ans);
temp.pop_back();
}
}
};

int main() {
int k = 3;
int n = 7;
Solution s;
vector < vector<int> > ans = s.combinationSum3(k, n);

for (int i = 0; i  <  ans.size(); i++) {
for (int j = 0; j  <  ans[i].size(); j++) {
printf("%d ", ans[i][j]);
}
printf("\n");
}

return 0;
}
``````
Copy The Code &

Input

cmd
k = 3, n = 7

Output

cmd
[[1,2,4]]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List();
helper(n, lists, new ArrayList<>(), 0, k, 1);
return lists;
}

private void helper(int n, List < List list, int currSum, int k, int currNum) {
if (list.size() == k) {
if (currSum == n) {
}
return;
}
for (int i = currNum; i  < = 9; i++) {
helper(n, lists, list, currSum + i, k, i + 1);
list.remove(list.size() - 1);
}
}
}
``````
Copy The Code &

Input

cmd
k = 3, n = 7

Output

cmd
[[1,2,4]]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const combinationSum3 = function(k, n) {
const ans = [];
combination(ans, [], k, 1, n);
return ans;
};

function combination(ans, comb, k, start, n) {
if (comb.length > k) {
return;
}
if (comb.length === k && n === 0) {
ans.push(comb.slice(0));
return;
}
for (let i = start; i  < = n && i <= 9; i++) {
comb.push(i);
combination(ans, comb, k, i + 1, n - i);
comb.pop();
}
}
``````
Copy The Code &

Input

cmd
k = 3, n = 9

Output

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

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
stack, nums, res = [(0, [], 0, k)], range(1, 10), []
while stack:
sm, tmp, index, k_val = stack.pop(0)
for i in range(index, len(nums)):
if sm + nums[i] < n and k_val > 0: stack.append((sm + nums[i], tmp + [nums[i]], i + 1, k_val - 1))
elif sm + nums[i] == n and k_val == 1: res.append(tmp + [nums[i]])
return res
``````
Copy The Code &

Input

cmd
k = 3, n = 9

Output

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

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0216_CombinationSumIII
{
public IList < IList<int>> CombinationSum3(int k, int n)
{
var results = new List < IList<int>>();
Helper(0, k, n, new List < int>(), results);
return results;
}

private void Helper(int index, int k, int n, IList < int> current, IList= k || n  <  0) return;

var start = index == 0 ? 1 : current.Last() + 1;
for (int i = start; i  < = n && i < 10; i++)
{
var newList = new List<int>(current);
Helper(index + 1, k, n - i, newList, results);
}
}
}
}
``````
Copy The Code &

Input

cmd
k = 4, n = 1

Output

cmd
[]