---

0216. 组合总和 III

• 标签：数组、回溯
• 难度：中等

题目链接

• 0216. 组合总和 III - 力扣

题目大意

描述：

给定两个整数 $n$ 和 $k$。

要求：

找出所有相加之和为 $n$ 的 $k$ 个数的组合，且满足下列条件：

• 只使用数字 $1$ 到 $9$
• 每个数字最多使用一次。

返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

说明：

• $2 \le k \le 9$。
• $1 \le n \le 60$。

示例：

• 示例 1：

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

• 示例 2：

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

解题思路

思路 1：回溯算法

这是一个典型的回溯算法问题。我们需要从数字 $1$ 到 $9$ 中选择 $k$ 个数字，使得它们的和等于 $n$，且每个数字最多使用一次。

我们可以使用回溯算法来解决这个问题：

1. 明确所有选择：对于每个位置，我们可以选择数字 $1$ 到 $9$ 中的任意一个（前提是该数字还没有被使用过）。
2. 明确终止条件：
   • 当选择的数字个数达到 $k$ 个时，检查这些数字的和是否等于 $n$。
   • 如果和等于 $n$，则找到一个有效组合，将其加入结果集。
   • 如果和大于 $n$，则剪枝，因为继续选择只会使和更大。
3. 将决策树和终止条件翻译成代码：
   • 定义回溯函数：backtracking(start, path, current_sum)，其中 $start$ 表示当前可以选择的数字范围，$path$ 表示当前选择的数字组合，$current\_sum$ 表示当前数字组合的和。
   • 对于每个位置，从 $start$ 开始枚举可选数字，避免重复选择。
   • 选择数字后递归搜索，搜索完成后撤销选择（回溯）。

思路 1：代码

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []  # 存放所有符合条件结果的集合
        path = []  # 存放当前符合条件的结果
        
        def backtracking(start, path, current_sum):
            # 终止条件：选择的数字个数达到 k 个
            if len(path) == k:
                if current_sum == n:  # 如果和等于 n，找到一个有效组合
                    res.append(path[:])  # 将当前组合加入结果集
                return
            
            # 剪枝：如果当前和已经大于 n，或者剩余数字无法凑够 k 个数字
            if current_sum > n or len(path) + (9 - start + 1) < k:
                return
            
            # 枚举可选数字
            for i in range(start, 10):  # 从 start 到 9
                path.append(i)  # 选择数字 i
                backtracking(i + 1, path, current_sum + i)  # 递归搜索
                path.pop()  # 撤销选择（回溯）
        
        backtracking(1, path, 0)  # 从数字 1 开始搜索
        return res

思路 1：复杂度分析

• 时间复杂度：$O(C(9,k) \times k)$，其中 $C(9,k)$ 表示从 $9$ 个数字中选择 $k$ 个数字的组合数。最坏情况下需要遍历所有可能的组合，每个组合需要 $O(k)$ 的时间来构造。
• 空间复杂度：$O(k)$，递归调用栈的深度最多为 $k$，每次递归需要 $O(1)$ 的额外空间。