题目描述
思路解析动画文字版
关键不是背模板，而是看懂为什么这题适合回溯 · 去重。
1. 排序，设定剩余目标 remain：排序 → [1,1,2,5,6,7,10]，相同数字相邻。target=8，每选一个数就从 remain 里减掉，remain 减到 0 即一个答案。每个数只用一次 → 递归传 i+1。
2. 选下标0的 1，remain 7：选下标 0 的 1 → remain = 8 − 1 = 7。
3. 更深层再选下标1的 1，remain 6：下一层(i+1)选下标 1 的 1 —— 它在更深层，不是同层重复，可以选 → remain 6。
4. 选下标4的 6 → 凑成 [1,1,6]：选下标 4 的 6 → remain 6 − 6 = 0 → 收集 [1,1,6]！
5. 关键帧 · 排序剪枝：撤销 6 回到 [1,1](remain 6)，下一个候选是下标5的 7：7 ＞ remain 6。排序后后面只会更大 → 直接 break 剪枝，不再往下试。
6. 关键帧 · 同层跳过重复的 1：下标0的 1 这条大分支全部走完，回到根。本想从下标1的 1 再开同样的分支，但它和同层下标0的 1 值相同 → 跳过（i ＞ start 且 nums[i]==nums[i−1]），否则会重复生成一整批 [1,…]。
7. 换从 2 开分支 → [2,6]：换从下标2的 2 开分支：2 → 6 → remain 0 → 收集 [2,6]。（同样方式，途中还找到 [1,2,5]、[1,7]）
8. 完成 · 4 个不重复组合：完整搜索得 4 个和为 8 的不重复组合：[[1,1,6],[1,2,5],[1,7],[2,6]]。靠「同层去重」防重复、「候选＞remain 就 break」剪枝。
把这句话记住，下次遇到同类题，就能更快选出方向。
边界三连：边界三连：极端输入先过一遍。
几个高频追问，记住答法。
参考代码
class Solution: def combinationSum2(self, candidates, target): candidates.sort() ans = [] def backtrack(start, remain, path): if remain == 0: ans.append(path[:]); return for i in range(start, len(candidates)): if i > start and candidates[i] == candidates[i - 1]: continue # 同层去重 if candidates[i] > remain: break # 排序后剪枝 path.append(candidates[i]) backtrack(i + 1, remain - candidates[i], path) # i+1: 只用一次 path.pop() backtrack(0, target, []) return ans复杂度
- 时间复杂度：O(2^n)，最坏每个数选/不选，O(2ⁿ)，排序剪枝后实际远小于此
- 空间复杂度：O(n)，递归深度 + path，O(n)（不计输出）
可套用的代码模板
模板不是死背，而是提醒你写代码前先把状态、转移和边界排好。
Python
# 组合总和II骨架 · 同层去重 + 剪枝candidates.sort()def backtrack(start, remain, path): if remain == 0: 收集 path; return for i in range(start, n): if i > start and c[i] == c[i-1]: continue # ① 同层去重 if c[i] > remain: break # ② 排序后剪枝 path.append(c[i]); backtrack(i+1, remain-c[i], path); path.pop() # i+1 只用一次易错点
面试追问把动画讲成自己的话
追问和「组合总和 I」的两点区别？
追问为什么排序+同层跳过能去重？
追问剪枝优化？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
单词搜索
LeetCode 79 · 中等 · 沿着 回溯 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题