LeetCode 216. 组合总和 III

2025-03-12 HGNULB 约 9 分钟

文章信息 8 个分类 · 3 个标签

分类

LeetCode CodeTop 中等 未解决 2-5 字节跳动 腾讯 LeetCode 75

标签

数组 回溯 组合问题

目录 收起 展开

题目描述

✅ 216. 组合总和 III

题意分析

要找出所有由 k 个互不相同的数字组成、且总和恰好为 n 的组合，可选数字只有 1 到 9，每个数字在一个组合里最多用一次，答案中不能出现重复的组合。

三条约束互相咬合：数字范围固定在 1 到 9、每个数只能用一次、组合不计顺序。第三条意味着 [1,2,6] 和 [2,1,6] 是同一个答案，只能保留一个。

规模极小：$2 \le k \le 9$，$1 \le n \le 60$。9 个数字的全部子集也才 512 个，穷举完全可行，所以本题考的不是复杂度，而是「如何不重不漏地枚举」以及「能加哪些剪枝」。

值域固定这一点还带来两个可直接算出的界：从 start 开始取 need 个数，最小和是 $start + (start+1) + \cdots + (start+need-1)$，最大和是 $9 + 8 + \cdots + (9-need+1)$。这两个界后面会直接变成剪枝条件。

边界要覆盖：n 小到不可能（如 k = 3、n = 5，最小和是 1 + 2 + 3 = 6，无解）、n 大到不可能（如 k = 2、n = 18，最大和是 9 + 8 = 17，无解）、以及 k = 9 时只有 [1..9] 一种组合且和恒为 45。

解法：递增回溯剪枝

核心思路

最直接的做法是枚举 1 到 9 的全部子集（512 个），逐个检查元素个数是否为 k、和是否为 n。这在本题规模下能过，但它把「不计顺序」这件事交给了子集枚举去保证，一旦把数字范围放大就没法直接推广。

更通用的做法是逐位决策：每一步从候选里挑一个数放进当前路径，路径长度达到 k 时检查和。可如果每一步都从 1 到 9 随便挑，[1,2,6] 会以 3! = 6 种排列被找到 6 次，重复解需要额外去重。

瓶颈就在这里。消除重复的标准手法是给答案定一个规范形式：规定路径里的数字必须严格递增。这样每个组合只对应唯一一条搜索路径，重复自然消失，代价只是给递归多传一个「下一个可选的最小数字」start。

于是状态定义为四元组：start 表示本层可选数字的下界，need 表示还要选几个数，remain 表示还差多少和，path 表示已经选好的数字。终止条件是 need == 0，此时只有 remain 也为 0 才是合法解。

有了 start 和 need，可以立刻算出这一层能凑出的和的取值范围：最小取 start 往上连续 need 个，即 $\frac{(2 \cdot start + need - 1) \cdot need}{2}$；最大取 9 往下连续 need 个，即 $\frac{(19 - need) \cdot need}{2}$。remain 落在这个闭区间之外时，这一整支子树连一个解都不会有，直接返回。这是本题最有效的剪枝。

循环上界也能收紧：还要选 need 个严格递增的数、最大只能到 9，所以本层选的数不能超过 10 - need，否则后面凑不够个数。再加上「num 超过 remain 就 break」（因为数字递增，后面只会更大），三层剪枝叠加后实际搜索的分支寥寥无几。

解题步骤

• 准备结果集 res 和可复用的路径容器 path，从 start = 1、need = k、remain = n 发起递归。path 全程只有一份，靠「加入—递归—弹出」来复原，避免每层都复制。
• 递归入口先处理终止：若 need == 0，说明已经选满 k 个数，此时再看 remain 是否为 0，是就把 path 复制一份加入结果集，然后无论如何都返回。必须复制，因为 path 后续还会被修改。
• 接着做区间剪枝：算出 minSum 与 maxSum，若 remain < minSum 或 remain > maxSum 就返回。前者表示即使取最小的几个数也已经超了，后者表示即使取最大的几个数也够不着，两种情况都不可能有解。
• 剪枝写在终止判断之后：先确认是否已经选满，再评估「还有没有可能凑成」。这也符合回溯的通用骨架——出口在最前，可行性判断紧随其后，最后才是枚举分支。
• 枚举本层数字 num，范围是 start 到 10 - need。上界写成 10 - need 是因为选完 num 后还要在 num + 1 到 9 之间取 need - 1 个数，num 太大就凑不够个数了。
• 循环体里先判 if (num > remain) break。因为 num 递增，一旦当前数字已经超过剩余目标，后面的数字只会更大，整个循环可以直接终止而不是 continue。
• 把 num 加入 path，递归调用 (num + 1, need - 1, remain - num)，返回后把 num 从 path 尾部弹出。递归起点用 num + 1 而不是 num，正是「每个数只能用一次且严格递增」的落地写法。

以 k = 3、n = 9 走一遍：入口状态是 start = 1、need = 3、remain = 9。minSum = (1 + 1 + 2) × 3 / 2 = 6，maxSum = (19 - 3) × 3 / 2 = 24，9 落在区间内。循环上界是 10 - 3 = 7。

取 num = 1，进入 (start = 2, need = 2, remain = 8)。这一层 minSum = (2 + 2 + 1) × 2 / 2 = 5，maxSum = 17，8 合法，循环上界是 8。先取 num = 2，进入 (3, 1, 6)：minSum = 3、maxSum = 9，6 合法，循环上界 9，依次试 3、4、5 都因为 remain 减完不为 0 而失败，试到 6 时 remain - 6 = 0 且 need 归零，记下 [1,2,6]；再试 7 时 7 > 6 触发 break。回到 (2,2,8) 层取 num = 3，进入 (4,1,5)：试 4 失败，试 5 成功，记下 [1,3,5]，试 6 时 break。再取 num = 4，进入 (5,1,4)：minSum = 5 已经大于 remain = 4，整支剪掉。num = 5、6、7、8 同理全被区间剪枝挡住。

回到最外层取 num = 2，进入 (3, 2, 7)：minSum = (3 + 3 + 1) × 2 / 2 = 7，恰好等于 remain，勉强合法。取 num = 3 进入 (4,1,4)，试 4 成功，记下 [2,3,4]；取 num = 4 进入 (5,1,3)，minSum = 5 > 3 被剪。

最外层再取 num = 3，进入 (4, 2, 6)：minSum = (4 + 4 + 1) × 2 / 2 = 9 > 6，整支剪掉；num = 4 到 7 的 minSum 只会更大，同样全被剪掉。搜索结束，结果为 [[1,2,6], [1,3,5], [2,3,4]]，与样例一致。

代码实现

class Solution {
    // 状态只需要记录当前可选起点、还需要选择几个数、剩余目标和，以及当前路径。
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(1, k, n, new ArrayList<>(), res);
        return res;
    }

    private void backtrack(
            int start, int need, int remain, List<Integer> path, List<List<Integer>> res) {
        if (need == 0) {
            if (remain == 0) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        int minSum = (start + start + need - 1) * need / 2;
        int maxSum = (19 - need) * need / 2;
        if (remain < minSum || remain > maxSum) {
            return;
        }

        for (int num = start; num <= 10 - need; num++) {
            if (num > remain) {
                break;
            }

            path.add(num);
            backtrack(num + 1, need - 1, remain - num, path, res);
            path.remove(path.size() - 1);
        }
    }
}

func combinationSum3(k int, n int) [][]int {
    // 状态只需要记录当前可选起点、还需要选择几个数、剩余目标和，以及当前路径。
    res := make([][]int, 0)
    path := make([]int, 0, k)

    var dfs func(start, need, remain int)
    dfs = func(start, need, remain int) {
        if need == 0 {
            if remain == 0 {
                pathCopy := make([]int, len(path))
                copy(pathCopy, path)
                res = append(res, pathCopy)
            }
            return
        }
        minSum := (start + start + need - 1) * need / 2
        maxSum := (19 - need) * need / 2
        if remain < minSum || remain > maxSum {
            return
        }

        for num := start; num <= 10-need; num++ {
            if num > remain {
                break
            }
            path = append(path, num)
            dfs(num+1, need-1, remain-num)
            path = path[:len(path)-1]
        }
    }

    dfs(1, k, n)
    return res
}

复杂度分析

• 时间复杂度：$O(C(9, k) \cdot k)$，搜索树的叶子对应 1 到 9 中所有大小为 k 的组合，共 $C(9,k)$ 个，每找到一个解要复制一份长度为 k 的路径；剪枝只会让实际访问的分支更少，不会更多。
• 空间复杂度：$O(k)$，不计结果集时只有一条长度不超过 k 的路径和同样深度的递归栈；由于 $k \le 9$，实际就是常数级。

关键点总结

• 「组合不计顺序」的去重手法是给答案定一条规范次序（这里是严格递增），并用一个 start 参数把它固化进搜索结构；这比先枚举全排列再去重要干净得多，也是所有组合型回溯题的共同起手式。
• 「每个数只能用一次」体现为递归传 num + 1，「可以重复使用」体现为传 num。这一个字的差别就是 39 和 40 两道题的分水岭，写之前先回题面确认。
• 值域固定的题目往往能推出可行区间的上下界，把「还差多少」和「最少能凑多少、最多能凑多少」一比就能整支剪掉；这类基于数量关系的剪枝远比逐个试更有效。
• 剪枝语句的位置很讲究：必须放在终止判断之后，否则会把 need 归零时的合法解一起挡掉。写回溯时要习惯性地问一句「这个判断放在出口前还是出口后」。
• 面试视角：本题写出朴素回溯只是及格线，被追问「还能怎么优化」时要能主动给出上下界剪枝、循环上界 10 - need、以及 num > remain 时 break（而不是 continue）三条，并解释为什么递增性保证了 break 是安全的。

易错点总结

• 错误写法：递归时传 num 而不是 num + 1 → k = 3、n = 9 时会产出 [1,1,7] 这类重复使用同一数字的解，而题目要求组合内数字互不相同。
• 错误写法：每层循环都从 1 开始而不是从 start 开始 → [1,2,6]、[1,6,2]、[2,1,6] 等 6 种排列都会被收进结果，答案里出现大量重复组合。
• 错误写法：Go 里把 path 切片直接 append 进结果集而不先 copy → 后续 append 会复用同一块底层数组，已收集的解被后来的数据覆盖，最终结果集里全是同一串数字。
• 错误写法：收集答案时直接 res.add(path) → Java 里加进去的是同一个列表引用，后续回溯把 path 弹空后，结果集里所有条目都会变成空列表。
• 错误写法：递归返回后忘记 path.remove(path.size() - 1) → 路径只增不减，第二个分支会带着上一个分支的残留数字继续搜，答案长度和内容全错。
• 错误写法：把 if (num > remain) break 写成 continue → 结果仍然正确，但因为数字是递增的，后面的 num 必然更大，白白多跑一整段无用循环，剪枝效果被浪费。
• 错误写法：循环上界写成 9 而不是 10 - need → 逻辑仍对，但会展开大量「剩余数字个数不足」的死分支，需要靠更深层的判断才发现无解。
• 错误写法：终止条件只判 remain == 0 就收集答案，不检查 need 是否为 0 → k = 3、n = 6 时会把只有两个数字的 [1,5] 也收进来，个数不符合要求。
• 错误写法：把 minSum 写成 start * need 或把 maxSum 写成 9 * need → 这两个界都比真实界宽松（因为数字必须互不相同），剪枝会失效一部分；虽然不会算错答案，但等于没做到位。

相似题目

题目	难度	考察点
39. 组合总和	中等	组合回溯
40. 组合总和 II	中等	组合回溯
77. 组合	中等	组合回溯
216. 组合总和 III	中等	组合回溯
LCR 080. 组合	中等	组合回溯
LCR 081. 组合总和	中等	组合回溯
LCR 082. 组合总和 II	中等	组合回溯