题目描述
思路解析动画文字版
k=2 写两层 for、k=3 写三层……可 k 是题目给的变量，写代码时根本不知道要套几层，嵌套循环这条路走不通。
另一个笨思路：1 到 9 每个数都「选 / 不选」，一共 2 的 9 次方 = 512 种组合，挨个检查个数和总和。这能跑，但白白枚举了大量个数都不对的子集——其实可以在搜索过程中边走边砍。
转折：用递归代替「不定层循环」。每选一个数，就从它后面继续选（start 保证只往后走、天然去重，不会冒出 [2,1,4]）；选够 k 个且剩余目标正好为 0 就收下，然后撤销刚才那一步回到上层换下一个。选→递归→撤销，三步循环。
关键提速：因为只能往后选、数越来越大，一旦当前数 x 已经超过「还差多少」(remain)，再往后的数更大、更不可能凑出来。直接 break 停掉整层，省下一大片死搜索。下面用 k=3、n=9 走一遍。
选 1 · path=[1]：先选 1，path=[1]，还差 remain=8。接下来 start=2，只能从 2 往后挑，1 不再回头看。还没够 k=3 个，继续往下选。
选 2 · path=[1,2]：再选 2，path=[1,2]，还差 remain=6。已经选了 2 个，再选 1 个就够 k=3 了——这第三个数必须正好等于 6 才行。
选 3 · 个数够了但和不对：选 3 → path=[1,2,3]，个数到 k=3 了，可总和 1+2+3=6 离 9 还差 3，remain=3≠0 不收。撤销 3，回到 [1,2] 换下一个。
撤销 3 → 试 4 · 还差 2：撤销 3、改选 4，path=[1,2,4]。个数够 k=3 了，可 remain=2≠0，不收。撤销 4，再换下一个。
撤销 4 → 试 5 · 还差 1：再换 5，path=[1,2,5]，remain=1≠0，还是不收。就差一点点——撤销 5，试下一个 6。
撤销 5 → 选 6 · 收下 [1,2,6]：试到 6：remain 正好减到 0，个数也够，收下 [1,2,6]！下一个候选 7 比 remain 还大，直接剪掉。
剪枝 · 7 > remain，停：剪枝实演：在 [1,2] 这层，6 之后该试 7。但 7 已经大于剩余目标，越往后越大、绝不可能凑成，直接 break 停掉（打叉那个）。回退，把 2 也撤销，换第二个数。
撤销 2 → 选 3 · path=[1,3]：回到第一层 [1]，撤销 2、改选 3，path=[1,3]，还差 remain=5。注意 2 已经从 path 撤走、重新变回「可选」。接着从 4 往后找第三个数。
[1,3] 后试 4 · 还差 1：在 [1,3] 后面先试 4，path=[1,3,4]。remain=1≠0，不收。撤销 4，换下一个 5。
撤销 4 → 选 5 · 收下 [1,3,5]：再试 5：remain 正好为 0，收下 [1,3,5]！之后 6 比 remain 大，剪掉。撤销回到 [1]，再换第二个数。
[1,4] 这层 · 第三个数都太大：改选 4，path=[1,4]，还差 4。可第三个数只能从 5 起，5 已经大于 4 了，整层一个都不用试，直接剪掉。1 打头的全部探完，撤销 1，换头。
换头 · 选 2 · path=[2]：回到最外层，1 已撤销、不在 path 里。改用 2 打头（start=3），还差 remain=7。start 保证不会再回头配到 1——这就是组合不重复的关键。
选 3 · path=[2,3]：在 [2] 后面选 3，path=[2,3]，还差 remain=4。已选 2 个，第三个数必须正好是 4。从 4 往后试。
选 4 · 收下 [2,3,4]：再选 4：remain 正好为 0，收下 [2,3,4]！接下来 5 比 remain 大被剪。撤销，[2] 后面换其他数。
[2,4] 这层 · 又被剪枝：改选 4，path=[2,4] 还差 3，第三个数从 5 起、已超 3，整层剪掉。2 打头探完。再换 3 打头：[3,4] 还差 2、第三个数从 5 起也超了……后面的头全被剪。
换头 · 选 3 · path=[3]：2 打头探完，撤销 2、改用 3 打头（start=4），还差 remain=6。从 4 往后接着配后两个数。
选 4 · path=[3,4]：选 4，path=[3,4]，还差 remain=2。第三个数得从 5 起，可 5 已经比 2 大了——下一步要被剪。
[3,4] 后第三数太大 · 剪掉：第三个数从 5 起、已超 remain=2，剪掉。3 后面更大的数打头只会差更多、更早被剪。3、4… 打头的分支几乎全被剪枝按住。
全部探完 · 收齐 3 个组合：3、4 打头往后的数都太大，被剪枝早早停掉。整棵搜索树走完，最终 3 个组合全部收齐。剪枝让我们没去碰一大片注定凑不成的死分支。
本题比普通组合多一个 remain（剩余目标）：它既是收不收的判据（=0 才收），又是剪枝的依据（x>remain 就停）。两个变量配合，搜索又准又快。
易错实演 · 忘了判 remain==0：负例：如果只看「够 3 个」就收，[1,2,3] 会被错收进结果——可它的和只有 6，不是 9。必须同时判 remain==0，否则全是垃圾组合。
边界三连：和太小（凑不够）或太大（超上限）都返回空。回溯天然处理这些边界——搜不到就是空，不用单独写特判。
面试常把本题和 LC39/LC40 放一起考，核心区别就在「传 x 还是 x+1」「池子和个数约束」上。
参考代码
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复杂度
- 时间复杂度：O(C(9,k) · k)，最多 C(9,k) 个组合，每个拷贝 O(k)
- 空间复杂度：O(k)，递归深度最多 k，path 最多 k 个数
可套用的代码模板
骨架记牢：for 从 start 起、递归传 x+1（不是 start+1）、选完 pop、x>remain 就 break。这是所有「固定个数 + 目标和」组合题的母模板。
模板
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()易错点
面试追问把动画讲成自己的话
追问和 LC39 组合总和（数字可重复使用、池子任意）有什么区别？
追问为什么用 remain 做减法，而不是把 path 求和再比？
追问如何保证结果不重复？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
递增子序列
LeetCode 491 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题