LeetCode LCR 081. 组合总和
目录
题目描述
题意分析
给一个元素互不相同的正整数数组
candidates和一个正整数target，要求列出所有和恰好等于target的选法。每个数字可以被选任意多次，最终返回的是「组合」而不是「排列」——[2,2,3]和[3,2,2]视为同一个答案，只能出现一次。
题目要的是全部方案本身，不是方案数量，这一点直接排除了计数型递推：必须把每一条选择路径真正走出来并记录下来。凡是「输出所有具体方案」的题，时间复杂度天然与答案规模同阶，只能靠搜索加剪枝。
数据规模给得极小：数组长度不超过 30，每个元素在
[2, 40]之间，target不超过 40。这组约束透露了两个关键信号。第一，元素全部大于等于 2 且为正，所以沿着一条路径累加的和是严格单调递增的，一旦超过target就再无回头可能，可以立刻剪掉——这也是为什么本题不需要担心「无限重复选取」导致的死循环。第二，target / min(candidates)最多 20 层，搜索树深度受控，指数级枚举在这个规模下完全跑得动。
去重是本题唯一真正的难点。同一个数可以重复使用，所以不能简单地「用过就标记」；而排列顺序不同却元素相同的路径必须被认为是重复。边界上要注意：数组元素互不相同（这是与「组合总和 II」的分水岭），
target可能小于所有元素从而无解，此时返回空列表而不是包含空组合的列表。
解法：回溯搜索
核心思路
最朴素的想法是：枚举每个位置放哪个数字，一层一层往下填，填到和等于
target为止。但这样枚举出来的是序列——2→2→3和3→2→2会被当成两条不同的路径分别记录。瓶颈就在这里：搜索天然带顺序，而答案不带顺序。
关键观察是：任何一个多重集合，都有且只有一种「按下标非递减排列」的写法。既然如此，只要强制搜索只沿着「下标不减」的方向前进，每个合法集合就恰好被走到一次，去重问题在搜索结构层面被彻底消解，完全不需要事后用哈希集合过滤。
于是给递归函数配三个参数：
s表示当前路径上已选数字之和，u表示本层允许选取的最小下标，t表示当前路径。要维持的不变量是：t中的下标序列非递减，s恒等于t中所有元素之和，且t里最后一个元素的下标不超过u。选中下标i之后向下递归时传入的仍然是i而不是i + 1，因为同一个数允许被再次选取；传入i而不是0，就把「回头选更小下标」这条路封死了。
递归的终止与剪枝同样由不变量推出：
s == target时当前路径正好构成一个答案，拷贝一份存入结果；s > target时由于元素全为正，继续往下走只会让s更大，这条分支必然无解，直接返回。这两个判断合起来保证了递归一定会终止。
解题步骤
- 准备结果容器与共享状态：
answer存放全部答案，candidates和target提升为成员变量。之所以不层层传参，是因为它们在整个搜索过程中恒定不变，作为共享状态可以让递归签名只保留真正会变化的三个量，读代码时一眼能看出「什么在变」。
- 命中答案时深拷贝路径：
s == target时执行answer.add(new ArrayList<>(t))。必须新建一份副本，因为t是全程复用的同一个对象，回溯时会被不断修改；直接把t的引用塞进结果，最后所有答案都会变成同一个空列表。
- 超额时立刻返回：
s > target直接剪枝。这一步的前提是元素全为正——如果允许出现 0 或负数，这个剪枝不成立，而且「可无限重复选取」会导致搜索不终止。
- 从下标
u开始横向枚举：for (int i = u; i < candidates.length; ++i)。起点是u而不是0，这正是去重的实现；终点是数组末尾，保证每个候选都有机会被选。
- 选择、递归、撤销三连：
t.add(c)记录选择，dfs(s + c, i, t)带着新的和向下走，t.remove(t.size() - 1)撤销选择。撤销这一步不可省——t是共享的可变对象，不还原就会把当前分支的残留带进兄弟分支。递归传入i而非i + 1，正是「同一元素可重复选取」的直接编码。
以
candidates = [2, 3, 6, 7]、target = 7走一遍。
根节点
dfs(s=0, u=0, t=[])，从下标 0 开始横向枚举。
先选下标 0 的 2，进入
dfs(2, 0, [2])；再选 2，进入dfs(4, 0, [2,2])；再选 2，进入dfs(6, 0, [2,2,2])；再选 2 得s=8 > 7，剪枝返回；改选下标 1 的 3 得s=9 > 7，剪枝；6、7 更大同样剪枝，于是[2,2,2]这一支全部失败，回溯到dfs(4, 0, [2,2])。
在
dfs(4, 0, [2,2])里改选下标 1 的 3，s = 4 + 3 = 7正好命中，记下第一个答案[2,2,3]；再试下标 2 的 6 得 10、下标 3 的 7 得 11，均剪枝。回溯到dfs(2, 0, [2])。
在
dfs(2, 0, [2])里改选 3 得dfs(5, 1, [2,3])，其下 3 得 8、6 得 11、7 得 12 全部超额，无解；再改选 6 得 8、7 得 9，均剪枝。注意这里u = 1，所以[2,3]之下不会再回头去选下标 0 的 2——[2,3,2]这条与[2,2,3]重复的路径被结构性地屏蔽了。
回到根节点，改选下标 1 的 3：
dfs(3,1,[3])之下 3 得 6，再往下 3 得 9、6 得 12、7 得 13 全超额；6 得 9、7 得 10 超额，这一支无解。改选下标 2 的 6：dfs(6,2,[6])之下 6 得 12、7 得 13，无解。改选下标 3 的 7：s = 7命中，记下第二个答案[7]。
最终
answer = [[2,2,3],[7]]。若把递归里的i误写成0，[3,2,2]、[2,3,2]都会被额外产出；若误写成i + 1，[2,2,3]就再也搜不到，答案只剩[7]。
代码实现
class Solution {
private List<List<Integer>> answer;
private int target;
private int[] candidates;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
answer = new ArrayList<>();
this.target = target;
this.candidates = candidates;
dfs(0, 0, new ArrayList<>());
return answer;
}
// s：当前路径和；u：本层允许选取的最小下标；t：当前路径。
private void dfs(int s, int u, List<Integer> t) {
if (s == target) {
// t 全程复用，必须深拷贝一份再存入结果。
answer.add(new ArrayList<>(t));
return;
}
if (s > target) {
// 元素全为正，继续向下只会更大，直接剪枝。
return;
}
for (int i = u; i < candidates.length; ++i) {
int c = candidates[i];
t.add(c);
// 传 i 而非 i + 1：同一元素允许重复选取；传 i 而非 0：禁止回头，实现组合去重。
dfs(s + c, i, t);
t.remove(t.size() - 1);
}
}
}
func combinationSum(candidates []int, target int) [][]int {
var answer [][]int
// s：当前路径和；u：本层允许选取的最小下标；t：当前路径。
var dfs func(s, u int, t []int)
dfs = func(s, u int, t []int) {
if s == target {
// t 底层数组会被后续 append 覆写，必须拷贝一份再存入结果。
answer = append(answer, append([]int(nil), t...))
return
}
if s > target {
// 元素全为正，继续向下只会更大，直接剪枝。
return
}
for i := u; i < len(candidates); i++ {
c := candidates[i]
t = append(t, c)
// 传 i 而非 i+1：同一元素允许重复选取；传 i 而非 0：禁止回头，实现组合去重。
dfs(s+c, i, t)
t = t[:len(t)-1]
}
}
var t []int
dfs(0, 0, t)
return answer
}
复杂度分析
- 时间复杂度：$O(S \times L)$，其中 $S$ 是答案个数，$L$ 是单个答案的平均长度，拷贝路径的开销摊在每个答案上。若用搜索树的粗略上界表达，设 $m$ 为候选个数、$d = target / \min(candidates)$ 为最大深度，则节点数不超过 $O(m^d)$；本题 $d \le 20$ 且剪枝极强，实际访问的节点远少于该上界。输出全部方案的题目，时间复杂度必然不低于答案总规模。
- 空间复杂度：$O(d)$，其中 $d = target / \min(candidates)$ 是递归最大深度，路径
t的长度与递归栈深度同阶。返回值answer本身是题目要求的输出，按惯例不计入额外空间。
关键点总结
- 「组合去重」的通用手法是给搜索强加一个下标非递减的方向，让每个多重集只有唯一一条生成路径。这个模板可以原样迁移到子集、组合、组合总和系列的所有题目，比事后用
Set去重高效得多，也是面试官想听到的答案。i还是i + 1决定了元素能否复用，是这一族题目的开关：可重复选取传i，每个元素最多用一次传i + 1。面试时被追问「如果每个数只能用一次呢」，改一个字符即可，能当场答出来是很直接的加分项。- 剪枝的合法性依赖题目约束：
s > target就返回，成立的前提是所有元素为正。面试中主动说出这个前提，比单纯写出剪枝更能体现严谨性。- 回溯三件套「选择 → 递归 → 撤销」必须成对出现，共享可变路径是回溯节省内存的原因，也是必须手动还原现场的原因。
- 记录答案时必须深拷贝，这是所有「收集路径」类回溯题的固定动作，与题目本身无关。
易错点总结
- 递归时传
0而不是i：candidates = [2,3]、target = 5会同时产出[2,3]和[3,2]，答案数量翻倍，判定直接失败。- 递归时传
i + 1而不是i：candidates = [2,3,6,7]、target = 7会丢掉[2,2,3]，只剩[7]，因为每个元素最多被用一次。- 忘记
t.remove(t.size() - 1)：candidates = [2,3]、target = 5时路径[2,2]失败后不还原，兄弟分支会带着残留的 2 继续，产出[2,2,3]这种和为 7 的非法结果。- 直接把
t存进answer而不深拷贝：candidates = [2,3,6,7]、target = 7最终会得到两个空列表[[],[]]，因为搜索结束时t已被回溯清空，两条结果指向同一个对象。- Go 里写成
answer = append(answer, t)：t与后续append共享底层数组，[2,2,3]存进去之后会被兄弟分支覆写成[2,3,6]之类的乱值，必须append([]int(nil), t...)拷贝。- 把
s > target的判断放在s == target之后却写成s >= target：candidates = [7]、target = 7时s == target的分支永远进不去，答案为空。- 用
s == target之外的方式判终止，例如先递归再判断：target = 1、candidates = [2]时递归会先入栈再判断，虽然结果正确，但少了s > target剪枝时candidates含小值会让深度暴涨到栈溢出。- 为了去重先排序再用
Set<List<Integer>>过滤：candidates = [2,3,6,7]、target = 7结果虽对，但搜索树规模仍是排列级，target稍大就超时，而且面试官会认为没抓住组合去重的本质。- 误以为数组已经有序而加了
candidates[i] > target - s就break：题目并未保证candidates有序，candidates = [7,2,3,6]时会在下标 0 处直接break，漏掉[2,2,3]；要用这个更强的剪枝，必须先自己排序。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 39. 组合总和 | 中等 | 与本题完全同题，代码可原样提交 |
| 40. 组合总和 II | 中等 | 候选含重复元素且每个只能用一次，需先排序并在同层跳过相同值 |
| 77. 组合 | 中等 | 固定长度 k 的组合，终止条件从「和达标」换成「长度达标」 |
| 216. 组合总和 III | 中等 | 候选固定为 1~9 且元素不可复用，同时限制个数与总和两个维度 |
| LCR 080. 组合 | 中等 | 与 77 同题，是本题去掉「和」约束后的最简形态 |
| LCR 082. 组合总和 II | 中等 | 与 40 同题，重点对比「传 i」与「传 i+1 加同层去重」的写法差异 |
| 78. 子集 | 中等 | 无任何和的限制，每个搜索节点都直接是答案，是本题模板的退化版 |
| 377. 组合总和 Ⅳ | 中等 | 顺序不同视为不同方案且只要方案数，应改用完全背包计数 DP 而非回溯 |