# 216. Combination Sum III

## Medium

***

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`

#### Solution 1:

Since we are taking number as already sorted and there is no duplicate as well. so can do it simply.

```python
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        l = [1,2,3,4,5,6,7,8,9]
        def recursion(l, start, path, result):
            if len(path) == k and sum(path) == n:
                result.append(path[:])
            for index in range(start, len(l)):
                if sum(path) + l[index] > n:
                    return
                recursion(l, index+1, path + [l[index]], result)
        result = []
        recursion(l,0,[], result)
        return result
```

**Solution 2:**

```python
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        result = []
        l = [1,2,3,4,5,6,7,8,9]
        def recursion(l, k ,start, n, path):
            if len(path) > k:
                return
            if  sum(path) == n and len(path) == k:
                result.append(path[:])
                return
            for index in range(start, len(l)):
                if index > start and l[index] == l[index-1]:
                    continue
                num = l[index]
                path.append(num)
                recursion(l, k, index+1, n, path)
                path.pop()
        recursion(l, k, 0, n, [])
        return result
```