# \[216]\[中等]\[回溯] 组合总和 III

## 题目描述

[216. 组合总和 III](https://leetcode-cn.com/problems/combination-sum-iii/)

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

* 所有数字都是正整数。
* 解集不能包含重复的组合。 

示例 1:

```
输入: k = 3, n = 7
输出: [[1,2,4]]
```

示例 2:

```
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
```

## 解题思路

相当于从`[1, 2, 3, 4, 5, 6, 7, 8, 9]`数组中找出k个数相加和为n的所有情况. 主要是考察剪枝:

* 重复情况剪枝, 一下层只探索本层元素之后的领域
* 找到k个数之后剪枝, 当前结果要么符合结果, 要么无法组成最后结果

注意下1到9全部使用的特殊情况.

```python
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        if n == 45:
            return [list(range(1, 10))]

        results = []

        def dfs(path, target, start):
            count = len(path)
            if count == k:
                if target == 0:
                    results.append(path[:])
                return

            for num in range(start, 10):
                path.append(num)
                dfs(path, target - num, num + 1)
                path.pop()

        dfs([], n, 1)
        return results
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/hui-su/216-zu-he-zong-he-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.