组合总和 III 图解题解

这道题到底在问什么

k

3

n

7

输出

[[1,2,4]]

n=9

[[1,2,6],[1,3,5],[2,3,4]]

先想最直接的笨办法

另一个笨思路：1 到 9 每个数都「选 / 不选」，一共 2 的 9 次方 = 512 种组合，挨个检查个数和总和。这能跑，但白白枚举了大量个数都不对的子集——其实可以在搜索过程中边走边砍。（动画第 4 步）

最优解：一步一步想明白

1. 3k=2 写两层 for、k=3 写三层……可 k 是题目给的变量，写代码时根本不知道要套几层，嵌套循环这条路走不通。
2. 4另一个笨思路：1 到 9 每个数都「选 / 不选」，一共 2 的 9 次方 = 512 种组合，挨个检查个数和总和。这能跑，但白白枚举了大量个数都不对的子集——其实可以在搜索过程中边走边砍。
3. 5转折：用递归代替「不定层循环」。每选一个数，就从它后面继续选（start 保证只往后走、天然去重，不会冒出 [2,1,4]）；选够 k 个且剩余目标正好为 0 就收下，然后撤销刚才那一步回到上层换下一个。选→递归→撤销，三步循环。
4. 6关键提速：因为只能往后选、数越来越大，一旦当前数 x 已经超过「还差多少」(remain)，再往后的数更大、更不可能凑出来。直接 break 停掉整层，省下一大片死搜索。下面用 k=3、n=9 走一遍。
5. 7remain = 9 − 1 = 8先选 1，path=[1]，还差 remain=8。接下来 start=2，只能从 2 往后挑，1 不再回头看。还没够 k=3 个，继续往下选。
6. 8remain = 8 − 2 = 6再选 2，path=[1,2]，还差 remain=6。已经选了 2 个，再选 1 个就够 k=3 了——这第三个数必须正好等于 6 才行。
7. 9len=3，remain = 6 − 3 = 3 ≠ 0 ✗选 3 → path=[1,2,3]，个数到 k=3 了，可总和 1+2+3=6 离 9 还差 3，remain=3≠0 不收。撤销 3，回到 [1,2] 换下一个。
8. 10len=3，remain = 6 − 4 = 2 ≠ 0 ✗撤销 3、改选 4，path=[1,2,4]。个数够 k=3 了，可 remain=2≠0，不收。撤销 4，再换下一个。
9. 11len=3，remain = 6 − 5 = 1 ≠ 0 ✗再换 5，path=[1,2,5]，remain=1≠0，还是不收。就差一点点——撤销 5，试下一个 6。
10. 12remain = 6 − 6 = 0 ✓ 收！试到 6：remain 正好减到 0，个数也够，收下 [1,2,6]！下一个候选 7 比 remain 还大，直接剪掉。
11. 13x=7 > remain（已为 0）→ break剪枝实演：在 [1,2] 这层，6 之后该试 7。但 7 已经大于剩余目标，越往后越大、绝不可能凑成，直接 break 停掉（打叉那个）。回退，把 2 也撤销，换第二个数。
12. 14remain = 8 − 3 = 5回到第一层 [1]，撤销 2、改选 3，path=[1,3]，还差 remain=5。注意 2 已经从 path 撤走、重新变回「可选」。接着从 4 往后找第三个数。
13. 15len=3，remain = 5 − 4 = 1 ≠ 0 ✗在 [1,3] 后面先试 4，path=[1,3,4]。remain=1≠0，不收。撤销 4，换下一个 5。
14. 16remain = 5 − 5 = 0 ✓ 收！再试 5：remain 正好为 0，收下 [1,3,5]！之后 6 比 remain 大，剪掉。撤销回到 [1]，再换第二个数。
15. 17start=5，5 > remain(=4) → 整层剪掉改选 4，path=[1,4]，还差 4。可第三个数只能从 5 起，5 已经大于 4 了，整层一个都不用试，直接剪掉。1 打头的全部探完，撤销 1，换头。
16. 18remain = 9 − 2 = 7回到最外层，1 已撤销、不在 path 里。改用 2 打头（start=3），还差 remain=7。start 保证不会再回头配到 1——这就是组合不重复的关键。
17. 19remain = 7 − 3 = 4在 [2] 后面选 3，path=[2,3]，还差 remain=4。已选 2 个，第三个数必须正好是 4。从 4 往后试。
18. 20remain = 4 − 4 = 0 ✓ 收！再选 4：remain 正好为 0，收下 [2,3,4]！接下来 5 比 remain 大被剪。撤销，[2] 后面换其他数。
19. 21start=5，5 > remain(=3) → 整层剪掉改选 4，path=[2,4] 还差 3，第三个数从 5 起、已超 3，整层剪掉。2 打头探完。再换 3 打头：[3,4] 还差 2、第三个数从 5 起也超了……后面的头全被剪。
20. 22remain = 9 − 3 = 62 打头探完，撤销 2、改用 3 打头（start=4），还差 remain=6。从 4 往后接着配后两个数。
21. 23remain = 6 − 4 = 2选 4，path=[3,4]，还差 remain=2。第三个数得从 5 起，可 5 已经比 2 大了——下一步要被剪。
22. 24start=5，5 > remain(=2) → 剪掉第三个数从 5 起、已超 remain=2，剪掉。3 后面更大的数打头只会差更多、更早被剪。3、4… 打头的分支几乎全被剪枝按住。
23. 25结果 = [[1,2,6],[1,3,5],[2,3,4]]3、4 打头往后的数都太大，被剪枝早早停掉。整棵搜索树走完，最终 3 个组合全部收齐。剪枝让我们没去碰一大片注定凑不成的死分支。
24. 28本题比普通组合多一个 remain（剩余目标）：它既是收不收的判据（=0 才收），又是剪枝的依据（x>remain 就停）。两个变量配合，搜索又准又快。
25. 31len=3 就收 → 误收 [1,2,3]负例：如果只看「够 3 个」就收，[1,2,3] 会被错收进结果——可它的和只有 6，不是 9。必须同时判 remain==0，否则全是垃圾组合。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def combinationSum3(self, k, n):
        ans = []
        def backtrack(start, path, remain):
            if len(path) == k:
                if remain == 0:
                    ans.append(path[:])
                return
            for x in range(start, 10):
                if x > remain:        # 剪枝
                    break
                path.append(x)
                backtrack(x + 1, path, remain - x)
                path.pop()
        backtrack(1, [], n)
        return ans

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> path;
        function<void(int,int)> backtrack = [&](int start, int remain) {
            if ((int)path.size() == k) {
                if (remain == 0) ans.push_back(path);
                return;
            }
            for (int x = start; x <= 9; ++x) {
                if (x > remain) break;        // 剪枝
                path.push_back(x);
                backtrack(x + 1, remain - x);
                path.pop_back();
            }
        };
        backtrack(1, n);
        return ans;
    }
};

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        backtrack(1, k, n, path, ans);
        return ans;
    }
    private void backtrack(int start, int k, int remain,
                           List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == k) {
            if (remain == 0) ans.add(new ArrayList<>(path));
            return;
        }
        for (int x = start; x <= 9; ++x) {
            if (x > remain) break;        // 剪枝
            path.add(x);
            backtrack(x + 1, k, remain - x, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

def bt(start, path, remain):
    if len(path) == k:
        if remain == 0: res.append(path[:])
        return
    for x in range(start, 10):
        if x > remain: break        # 剪枝
        path.append(x)
        bt(x + 1, path, remain - x)  # 关键 x+1
        path.pop()

复杂度

面试官可能追问