216. 组合总和 III Medium

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

只使用数字 1 到 9

每个数字最多使用一次

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

示例 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，没有有效的组合。

解题思路

输入：两个整数 k 和 n，要求从 1 到 9 之间选择 k 个不同的数字，和为 n。

输出：返回所有可能的组合（顺序无关，但数字不能重复使用）。

这道题属于 组合型回溯 问题。

我们从 9 开始（因为题目中数字是 1~9 且不能重复）尝试往路径里选数字。
每次选择一个数字 j 后，把它放到路径 path 里，并更新当前和 t。
然后继续递归选择 j-1 及以下的数字。
如果当前路径长度已经等于 k 且和等于 n，说明找到了一种有效的组合，把它保存到 ans 里。
如果当前和超过 n，或者剩下的数字都不足以凑成和，直接剪枝返回。

回溯三问

当前操作？
- 在当前位置 i（表示可以选择的最大数字）中，尝试选择当前数字 j（j ∈ [i, 1]），并将它加入路径 path。
- 也就是把数字 j 放到路径中，表示“我选择了这个数字”。
子问题？
- 选择了数字 j 之后，需要继续递归选择剩余的数字（j-1 到 1）以补足组合。
- 同时累计当前和 t，继续递归搜索，直到路径长度等于 k。
下一个子问题？
- 下一步递归就是 dfs(j-1, t+j)，表示从 j-1 开始继续选择剩余数字，并更新当前和。

剪枝条件

如果当前和 t 已经大于目标和 n，就直接剪枝返回，不再继续递归。
如果剩余的数字数量不足以填满剩余的组合（即 (i - d + 1 + i) * d // 2 < n - t），也直接剪枝返回。

代码实现

pythonjavascript

python

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []       # 存储最终的结果
        path = []      # 当前的组合路径

        # 回溯函数
        def dfs(i, t):
            # 剪枝1：如果已经选的数字和 t 大于目标 n，直接剪枝
            if t > n:
                return

            # 剪枝2：如果剩余的数字（i到1）都选上，和依然无法凑到 n，也剪枝
            # 计算公式：用等差数列的和公式（首项 i - d + 1，末项 i，共 d 项）
            d = k - len(path)
            min_sum = (i - d + 1 + i) * d // 2  # i-(d-1) 到 i 的和
            if min_sum < n - t:
                return

            # 如果选够了 k 个数，并且总和等于 n，加入答案
            if len(path) == k and t == n:
                ans.append(path.copy())
                return

            # 枚举从 i 到 1 的所有数字（从大到小）
            for j in range(i, 0, -1):
                path.append(j)            # 当前操作：选择数字 j
                dfs(j - 1, t + j)        # 子问题：从 j-1 开始继续选择
                path.pop()               # 回溯：撤销选择

        dfs(9, 0)  # 从数字 9 开始递归
        return ans

javascript

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
const combinationSum3 = function(k, n) {
    const ans = [];
    const path = [];

    function dfs(i, t) {
        if (t > n) return;

        const d = k - path.length;
        if ((i - d + 1 + i) * d / 2 < n - t) return;

        if (path.length == k && t == n) {
            ans.push([...path]);
            return;
        }

        for (let j = i; j > 0; j --) {
            path.push(j);
            dfs(j - 1, t + j);
            path.pop()
        }
    }
    dfs(9, 0);
    return ans;
};

复杂度分析

时间复杂度：O(k * 9^k)

空间复杂度：O(k)

链接

216 国际版

216 中文版

216. 组合总和 III Medium ​

解题思路 ​

回溯三问 ​

剪枝条件 ​

代码实现 ​

复杂度分析 ​

链接 ​