LeetCode 216. 组合总和 III

1. 问题描述：

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

1. 只使用数字 1 到 9。
2. 每个数字最多使用一次。
3. 返回所有可能的有效组合的列表。
4. 组合不能包含相同的元素，且组合可以以任何顺序返回。

输入格式：

输入两个整数 k 和 n。

输出格式：

返回一个包含所有有效组合的列表。

示例输入与输出：

示例 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
没有其他符合的组合了。

示例 3： 输入：
k = 4, n = 1

输出：
[]

解释：
在 [1,9] 范围内使用 4 个不同的数字，最小和是 1+2+3+4 = 10，因为 10 > 1，没有有效的组合。

2. 整体思路

回溯算法是一种通过探索所有可能的候选解来找出所有符合条件解的算法。对于本题来说，我们要从 1 到 9 这 9 个数字中选取 k 个数字，使得它们的和为 n，可以按以下步骤进行：

确定搜索空间：

由于只能使用 1 到 9 的数字，且每个数字最多用一次，所以我们的搜索空间就是从 1 到 9 这 9 个数字。

定义状态变量和递归函数：

• 需要一个列表（比如 path）来记录当前已经选取的数字组合，用于记录走过的 “路径”。
• 定义一个变量（比如 sum_）来记录当前路径上数字的总和，方便判断是否满足和为 n 的条件。
• 定义递归函数（比如 backtracking），函数接受参数来表示当前已经选取的数字个数（用于判断是否选够了 k 个数字）、当前的搜索起点（避免重复选取数字）等。

回溯过程：

• 在递归函数中，首先判断当前路径上数字的个数是否达到了 k 个，并且总和是否等于 n，如果满足这两个条件，就将当前的数字组合 path 添加到结果列表中。
• 然后从搜索起点开始，依次尝试选取每个数字，将其加入到当前路径 path 中，更新总和 sum_，接着进行下一层递归（注意传入更新后的参数，比如选取数字个数加 1，新的搜索起点等），递归结束后需要回溯，也就是把加入的数字从 path 中移除，总和 sum_ 也减去相应的值，这样可以继续尝试其他的选择。

3. 代码

def combinationSum3(k, n):
    result = []  # 存储所有满足条件的组合
    path = []    # 当前组合路径

    # 回溯函数
    def backtrack(start, target):
        # 如果当前路径长度等于 k 并且和等于 n，将结果加入结果集
        if len(path) == k and target == 0:
            result.append(path[:])
            return
        # 剪枝条件：如果路径长度超过 k，或剩余目标小于 0，提前结束
        if len(path) > k or target < 0:
            return

        # 从当前数字开始搜索，避免重复使用数字
        for i in range(start, 10):  # 数字范围 1-9
            path.append(i)             # 选择当前数字
            backtrack(i + 1, target - i)  # 递归搜索，下一次从 i+1 开始
            path.pop()                 # 回溯，撤销选择

    # 从数字 1 开始搜索
    backtrack(1, n)
    return result

# 示例测试
print(combinationSum3(3, 7))  # 输出: [[1, 2, 4]]
print(combinationSum3(3, 9))  # 输出: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
print(combinationSum3(4, 1))  # 输出: []