组合总和 III 如何限制数字范围、数量和目标和？

简化版

组合总和 III 要从 1..9 中选 k 个互不重复的数，使它们和为 n。回溯状态记录 start、剩余个数和剩余和；选择数字 i 后递归到 i + 1，当剩余个数为 0 且剩余和为 0 时收集答案。

详细版

这题是组合问题和组合总和的交叉：组合要求顺序无关且数字不能重复，所以要用 start；目标和要求每次选择后减少 remain；数量要求路径长度必须恰好为 k。

剪枝可以从三个方向做：当前数字超过剩余和时停止；剩余数字数量不够时停止；剩余和小于可选最小和或大于可选最大和时返回。因为候选范围固定为 1..9，复杂度上限不大，但面试会追问这些剪枝的正确性。

完整版教学

一、这题同时限制三个维度

题目要求从 1..9 里选 k 个数，和为 n。例如 k = 3, n = 7，答案是：

[1,2,4]

这里有三个限制：

限制	含义
数字范围	只能用 1 到 9
数量	必须恰好选 k 个
和	总和必须等于 n

因此回溯状态要同时维护“从哪里开始选、还要选几个、还剩多少和”。

二、为什么仍然用 start

组合总和 III 的数字不能重复，且组合不关心顺序。选择 i 后，下一层只能从 i + 1 开始，这样既不会重复使用 i，也不会产生 [1,2,4] 和 [2,1,4] 这样的顺序重复。

path = [1]
下一层只能选 2..9
path = [1,2]
下一层只能选 3..9

记忆钩子：只要是“不重复选 + 顺序无关”，优先想到 start 和 i + 1。

三、终止条件必须同时满足数量和剩余和

只有当 path.size() == k 且 remain == 0 时才收集答案。下面两种情况都不能收：

path.size() == k, remain != 0  -> 数量够了但和不对
remain == 0, path.size() != k  -> 和够了但数量不对

例如 k=3, n=9，路径 [4,5] 的和已经是 9，但只选了 2 个数，不能作为答案。

四、基础剪枝：超过剩余和就停止

因为候选数字按递增枚举，如果当前 i > remain，后面的数字只会更大，继续尝试没有意义，可以 break。

if (i > remain) break;

这条剪枝依赖数字都是正数，且枚举顺序递增。如果候选里有负数，就不能这么剪。

五、数量剪枝和上下界剪枝

还需要 need = k - path.size() 个数，从 i..9 至少要有 need 个可选数字，所以循环上界可以限制为：

i <= 9 - need + 1

还可以用最小可能和、最大可能和剪枝：

最小和：start + (start + 1) + ... 取 need 个
最大和：9 + 8 + ... 取 need 个

例如还需要 3 个数，从 6 开始最小和是 6+7+8=21；如果 remain=15，这条分支必然失败。

六、代码模板

List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(1, k, n, new ArrayList<>(), res);
    return res;
}

void backtrack(int start, int k, int remain, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == k) {
        if (remain == 0) res.add(new ArrayList<>(path));
        return;
    }

    int need = k - path.size();
    if (remain < minSum(start, need) || remain > maxSum(need)) return;

    for (int i = start; i <= 9 - need + 1; i++) {
        if (i > remain) break;
        path.add(i);
        backtrack(i + 1, k, remain - i, path, res);
        path.remove(path.size() - 1);
    }
}

int minSum(int start, int count) {
    return (start + start + count - 1) * count / 2;
}

int maxSum(int count) {
    return (9 + 9 - count + 1) * count / 2;
}

如果面试时间有限，可以只写基础剪枝；若追问优化，再补上下界剪枝。

七、常见误区与追问

误区：把它当作可重复选择的组合总和。 数字 1 到 9 每个最多用一次，递归必须传 i + 1。
误区：remain 为 0 就立刻收集。 还必须保证已经选了恰好 k 个数。
误区：path 长度达到 k 后继续递归。 数量已经满了，应立即判断并返回。
追问：为什么 i > remain 可以 break？ 后续数字更大且全为正数，不可能让剩余和回到 0。
追问：数量剪枝怎么推？ 还需要 need 个数，i..9 至少要剩 need 个位置，所以 i <= 9 - need + 1。
追问：为什么可以用等差数列剪枝？ 从当前 start 取 need 个最小数给下界，从 9 往下取 need 个最大数给上界。

八、加强记忆

组合总和 III 可以记成“三把锁”：范围锁在 1..9，数量锁在 k，目标锁在 remain。因为它仍是组合题，所以用 start 固定顺序，选择后递归到 i + 1；因为它有目标和，所以每次扣减 remain，超过剩余和就停止；因为它有数量限制，所以终止和剪枝都要看 need。把这三把锁讲清楚，代码就不会写成组合总和 I 或普通组合题。

简化版

详细版