题目描述
思路解析
一句话答案：LeetCode 39 组合总和用回溯加剪枝：candidates 升序排序后递归，维护剩余目标 remain，从下标 start 往后试数；同一个数可无限次重复选，故递归传当前下标 i 而不是 i + 1；candidates[i] 大于 remain 即 break 整层。时间约 O(N^(T/M))，递归深度 O(T/M)。
这道题和普通组合题差在哪
给定候选数组和目标值 target，找出所有和恰好等于 target 的组合。它有两个特殊设定：其一，同一个数可以重复选任意次——示例 candidates 为 [2,3,6,7]、target 为 7 时，答案是 [2,2,3] 和 [7]，前者把 2 用了两次；其二，组合之间不许重复，[2,2,3] 和 [3,2,2] 只能算一个。一边允许「元素重复」，一边禁止「组合重复」，解法必须同时兼顾这两条，这正是本题的看点。
递归传 i 而不是 i + 1 是题眼
回溯每选中下标 i 的数，下一层递归的起点仍然传 i——就这一个字符的差别，决定了能否重复选。传 i，下一层还能再选到自己，[2,2,3] 才凑得出来；改传 i + 1，就退化成每个数只能用一次的 LC40 组合总和 II，含重复元素的解会整批丢失。同时用 remain 记剩余目标，每层减去所选的数，减到 0 说明恰好凑满，把当前 path 的副本收进结果并返回。
start 下标怎么保证组合不重复
防止 [2,2,3] 和 [3,2,2] 被当成两个答案的手法，与子集类问题同源：每层只从 start 往后选，绝不回头选前面的下标。于是任何一条路径里元素的下标非降，每个组合唯一对应「按下标顺序选取」这一种走法。换个角度说，重复组合的根源是同一批数换个顺序再来一遍，而 start 直接封死了回头路——去重不靠事后比对结果集，而是在生成阶段就杜绝。
排序之后为什么敢 break 整层
剪枝的依据是升序：一旦当前候选 candidates[i] 已经大于 remain，选它必然超出目标；而排序保证它后面的候选只会更大，同样全部超标——所以可以 break 直接结束这一层循环，而不是 continue 逐个再试。没有排序就没有「后面更大」的保证，只能 continue，会白白探索大量注定失败的分支。这一步不改变答案集合，只砍掉无效搜索，是回溯题「先排序再剪枝」的典型配合。
复杂度与常见翻车点
搜索树规模约为 O(N^(T/M))：N 是候选个数，T 是 target，M 是最小候选值——最坏情况下每层至多 N 个分支、深度可达 T/M（一直选最小的数）。递归深度即 path 的最长长度，空间 O(T/M)。三个高频错误：递归传成 i + 1，漏掉需要重复选的解；每层都从头开始选，产生换序重复的组合；不剪枝、只靠递归到底再判和，分支爆炸容易超时。最后别忘了收集答案时存 path 的副本，而不是引用本身。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这三个动作：选 → 超了剪 → 正好收。下面每一帧就是其中一个动作。
开局：path 为空，还没收集任何结果。剩余要凑的和 = target = 7。候选 [2,3,6,7] 都可选，且可重复选。
选下标 0 的 2 放进 path。当前和 2，剩余还要凑 5。继续从这个下标往后(含自己)选——所以同一个数能再选。
选下标 0 的 2 放进 path。当前和 4，剩余还要凑 3。继续从这个下标往后(含自己)选——所以同一个数能再选。
选下标 0 的 2 放进 path。当前和 6，剩余还要凑 1。继续从这个下标往后(含自己)选——所以同一个数能再选。
剩余只剩 1，但下标 0 的候选 2 比它还大——再选必然超 target，画 ✗ 剪掉（它后面的更大，也一起放弃）。
这条路探完，把 2 拿出来回退（撤销选择），换下一个候选继续试。path 退回 [2,2]。
选下标 1 的 3 放进 path。当前和 7，剩余还要凑 0。正好凑满！
剩余 = 0，path [2,2,3] 的和正好 = 7！收进结果 res。这是一条合法组合。
这条路探完，把 3 拿出来回退（撤销选择），换下一个候选继续试。path 退回 [2,2]。
剩余只剩 3，但下标 2 的候选 6 比它还大——再选必然超 target，画 ✗ 剪掉（它后面的更大，也一起放弃）。
这条路探完，把 2 拿出来回退（撤销选择），换下一个候选继续试。path 退回 [2]。
选下标 1 的 3 放进 path。当前和 5，剩余还要凑 2。继续从这个下标往后(含自己)选——所以同一个数能再选。
剩余只剩 2，但下标 1 的候选 3 比它还大——再选必然超 target，画 ✗ 剪掉（它后面的更大，也一起放弃）。
这条路探完，把 3 拿出来回退（撤销选择），换下一个候选继续试。path 退回 [2]。
剩余只剩 5，但下标 2 的候选 6 比它还大——再选必然超 target，画 ✗ 剪掉（它后面的更大，也一起放弃）。
这条路探完，把 2 拿出来回退（撤销选择），换下一个候选继续试。path 已空，回到最外层。
选下标 1 的 3 放进 path。当前和 3，剩余还要凑 4。继续从这个下标往后(含自己)选——所以同一个数能再选。
选下标 1 的 3 放进 path。当前和 6，剩余还要凑 1。继续从这个下标往后(含自己)选——所以同一个数能再选。
剩余只剩 1，但下标 1 的候选 3 比它还大——再选必然超 target，画 ✗ 剪掉（它后面的更大，也一起放弃）。
这条路探完，把 3 拿出来回退（撤销选择），换下一个候选继续试。path 退回 [3]。
剩余只剩 4，但下标 2 的候选 6 比它还大——再选必然超 target，画 ✗ 剪掉（它后面的更大，也一起放弃）。
这条路探完，把 3 拿出来回退（撤销选择），换下一个候选继续试。path 已空，回到最外层。
选下标 2 的 6 放进 path。当前和 6，剩余还要凑 1。继续从这个下标往后(含自己)选——所以同一个数能再选。
剩余只剩 1，但下标 2 的候选 6 比它还大——再选必然超 target，画 ✗ 剪掉（它后面的更大，也一起放弃）。
这条路探完，把 6 拿出来回退（撤销选择），换下一个候选继续试。path 已空，回到最外层。
选下标 3 的 7 放进 path。当前和 7，剩余还要凑 0。正好凑满！
剩余 = 0，path [7] 的和正好 = 7！收进结果 res。这是一条合法组合。
搜索结束。所有从 start 往后、不超 target 的路径都试过了，收集到 2 条组合：[[2,2,3],[7]]。
边界先想清：凑不出、重复选、多解。
两个高频追问。
参考代码
def combinationSum(candidates, target): candidates.sort() # 升序，便于剪枝 res, path = [], [] def bt(start, remain): if remain == 0: res.append(path[:]); return for i in range(start, len(candidates)): if candidates[i] > remain: break # 剪枝 path.append(candidates[i]) bt(i, remain - candidates[i]) # 传 i: 可重复选 path.pop() # 回溯 bt(0, target) return res复杂度
- 时间：O(N^(T/M))，N=候选数，T=target，M=最小候选；搜索树规模
- 空间：O(T/M)，递归深度 = path 最长长度
易错点
面试追问把动画讲成自己的话
追问和 LC40（组合总和 II）有什么区别？
追问为什么排序后能用 break 剪枝？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
全排列
LeetCode 46 · 中等 · 沿着 回溯 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题