## Description

https://leetcode.com/problems/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 = 7Output:[[1,2,4]]Explanation:1 + 2 + 4 = 7 There are no other valid combinations.

**Example 2:**

Input:k = 3, n = 9Output:[[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 = 1Output:[]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.

**Example 4:**

Input:k = 3, n = 2Output:[]Explanation:There are no valid combinations.

**Example 5:**

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

**Constraints:**

`2 <= k <= 9`

`1 <= n <= 60`

## Python Solution

Depth-first search.

```
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
nums = [i for i in range(1, 10)]
nums.sort()
combinations = []
self.dfs(nums, 0, k, n, [], combinations)
return combinations
def dfs(self, nums, index, k, target, combination, combinations):
if k == 0 and target == 0:
combinations.append(list(combination))
return
if k == 0 or target <= 0:
return
for i in range(index, len(nums)):
combination.append(nums[i])
self.dfs(nums, i + 1, k - 1, target - nums[i], combination, combinations)
combination.pop()
```

- Time Complexity: O(2^n *n).
- Space Complexity: O(N).

Ubuntu was originally a terminal-based operating system, but over time Linux slowly introduced the graphical user interface to its operating systeread more , with screen shot and code snipets at

How to Shut Down Ubuntu