39. 组合总和（Combination Sum）
难度：中等 | 主题：回溯 + 排序剪枝，可重复选
题目
给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合。candidates 中的同一个数字可以无限制重复被选取。
示例
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
思路
先讲个故事：自助餐随便拿，但不能拿重样
自助餐厅里有一排菜：[2元区, 3元区, 6元区, 7元区]。
你拿着 7 块钱，每样菜可以拿无限份（只要不超预算），但拿菜的顺序不重要——拿一份 2 元菜再拿一份 3 元菜，和反过来一样。
关键约束：只能从左往右走，不能回头。这样 [2,3] 和 [3,2] 就不会同时出现。
引导式推导：从可重复到剪枝
第 1 步：和第 77 题的区别
77 题组合是 [1, n] 中选 k 个，每个数只能用一次（递归时 i+1）。
本题每个数可以用无限次（递归时 i 不动）。
graph TD A["77 组合"] --> B["选过了就不能再选"] A --> C["backtrack(i+1)"] D["39 组合总和"] --> E["选了还能再选"] D --> F["backtrack(i)"]
第 2 步：排序剪枝
先把 candidates 排序。如果当前数 x > remain，后面更大的数一定也超——直接 break。
graph TD A["排序后: [2,3,6,7]"] --> B["选 2 → remain=5"] B --> C["选 2 → remain=3"] C --> D["选 2 → remain=1"] D --> E["选 3 → 超了! break"] C --> F["选 3 → remain=0 ✓"] B --> G["选 3 → remain=2"] G --> H["选 2 → remain=0 ✓"]
第 3 步：剪枝前后对比
不剪枝：每个分支都会走到底，很多无效探索
剪枝后：x > remain 时整层砍掉（因为排序保证了后面的更大）
代码
class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
candidates.sort()
res, path = [], []
def dfs(start: int, remain: int):
if remain == 0:
res.append(path[:])
return
for i in range(start, len(candidates)):
x = candidates[i]
if x > remain:
break
path.append(x)
dfs(i, remain - x)
path.pop()
dfs(0, target)
return res
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(N^(T/M)) | N=数组长, M=最小值, T=target |
| 空间 | O(T/M) | 递归栈深度（最坏全选最小值） |
实战考量
频率分析
出现在：字节/美团 一面回溯必考题，约 40% 常会从这题开始考察修剪优化意识。30→40→90 系列的先导题。
延伸思考
Q：为什么 dfs(i, remain - x) 下标不改？
A：允许重复选同一个元素。[2,2,3] 中 2 被选了两次，递归时 start 不能 +1。
Q：为什么排序后 x > remain 可以 break？
A：排序后后面的元素 ≥ x，最小的都超了，后面的更大，全部砍掉。
Q：和 40 题的区别是什么？
A：39 无重复元素且可重复选（dfs(i)）；40 有重复元素且不可重复选（dfs(i+1) + 同层去重）。
Q：为什么用 start 参数控制不回头？
A：组合不考虑顺序，[2,3] 和 [3,2] 是同一个组合。start 保证只往后选，自然避免了顺序重复。
Q：如果 candidates 里有 0 呢？
A：按题目约定所有元素为正整数。如果有 0 会导致无限递归（选 0 永远不减 remain）。
易错点
-
dfs(i, ...)不是dfs(i+1, ...) -
排序是剪枝前提
-
res.append(path[:])拷贝非引用 -
x > remain用break（后面都更大），不是continue
生活类比
自助餐的智慧
你拿着 7 块钱进了自助餐厅。
先看一眼价目表，从最便宜的菜开始看（排序）。
如果连最便宜的都买不起了，更贵的想都别想（剪枝）。
拿起一份菜放到盘子里，如果超预算了就放回去试试别的（回溯）。
排序 + 剪枝 = 先看价目表，超了就扭头走人。
相关题目
→ 返回题单：LeetCode学习路线图 > 十、回溯
速记卡（面试闪卡）
Q1：一句话讲清「39. 组合总和（Combination Sum）」到底是什么？
A：无重复数组凑出和为 target 的所有组合，元素可无限选，回溯+排序剪枝搞定。
Q2：一、题目：自助餐凑账单 —— 怎么理解？
A：像拿 7 块钱在自助餐每样无限拿：给无重复 candidates 与 target，求所有和为 target 的组合（Combination Sum）。[2,3,6,7] target7 → [[2,2,3],[7]]。
Q3：二、思路：只往右不回头 —— 怎么理解？
A：像拿菜只能从左往右、不能回头，这样 [2,3] 和 [3,2] 不会重复（No-backtrack ordering）。每个数可重复选（递归 start 不变），组合不考虑顺序。
Q4：三、代码：dfs + 排序剪枝 —— 怎么理解？
A：像先看价目表再拿：candidates 排序，x>remain 直接 break 砍整层（Pruning）。dfs(i,remain-x) 下标不改允许重复，path 满则拷贝入结果（Backtracking）。
Q5：四、复杂度与实战：回溯必考 —— 怎么理解？
A：时间 O(N^(T/M))、空间 O(T/M)。字节/美团一面回溯必考约 40%，考修剪优化意识（Pruning）。30→40→90 系列先导；40 题有重复不可重复选。
Q6：核心速记主线有哪些？
-
核心：元素可无限选、组合不考虑顺序
-
去重：start 参数只往后选，避免 [2,3]/[3,2] 重复
-
剪枝：排序后 x>remain 直接 break
-
代码：dfs(i,remain-x) 下标不改；res.append(path[:]) 拷贝
-
关联：40 有重复不可重复选；77 固定长度
口诀
A：组合总和回溯搞，
自助餐里随便挑；
排序剪枝超就砍，
重复选取也能好。