本文共 1228 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 到 9 的正整数，并且每种组合中不存在重复的数字。

方法思路

我们可以使用递归的方法来解决这个问题。递归的思路是，先处理当前的数字，然后递归处理剩下的部分。具体步骤如下：

解决代码

from typing import List
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        path = []
        
        def dfs(start, current_sum):
            if len(path) == k and current_sum == n:
                res.append(path.copy())
                return
            for i in range(start, 10):
                if current_sum + i > n:
                    continue
                if len(path) < k and (current_sum + i + (9 - i) * (k - len(path) - 1) < n):
                    continue
                path.append(i)
                dfs(i + 1, current_sum + i)
                path.pop()
                
        dfs(1, 0)
        return res

代码解释

• 递归函数 dfs：这是核心的递归函数，负责进行深度优先搜索。它接受当前的起始数字和当前的和。
• 路径记录：使用 path 列表来记录当前的组合路径，确保每个组合中的数字不重复。
• 剪枝条件：在递归过程中，检查当前路径是否超过剩余和的限制，避免无效递归。
• 结果收集：当满足条件时，将当前路径添加到结果列表中。

通过这种方法，我们可以高效地找到所有满足条件的组合。