组合总和
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序 返回这些组合。
candidates 中的同一个 数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1
示例 2
示例 3
模拟答题者思考
1. 我先想暴力：从 candidates 中任意选若干个（可重复），枚举所有子序列，检查总和是否等于 target——思路对，但组合爆炸，且 [2,3] 与 [3,2] 会被当成两种答案。
2. 重复在哪里？每多选一个数，子问题变成「在剩余目标和下继续选数」；很多分支在 remain 变负后仍会继续深搜，白白浪费。
3. 关键转化：用 start 控制「只从当前下标往后选」，既避免 [2,3]/[3,2] 重复，又允许同一数重复用（递归传 i 而非 i+1）；remain == 0 收集，remain < 0 剪枝。
4. 例 1 candidates=[2,3,6,7], target=7：先试 2（remain=5）再试 2（remain=3）再试 3（remain=0）→ 得到 [2,2,3]；另一路直接选 7 → [7]。
5. 可先对 candidates 排序，遇到 candidates[i] > remain 时后面更大可提前 break；题目保证答案 < 150 组，剪枝后可行。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
path | list<int> | 定义：当前正在构造的组合（已选数字序列） 维护：DFS 每层在末尾追加一个候选数，回溯时 pop 撤销更新：尝试 candidates[i] 时 append；该分支探索完毕后 pop |
remain | int | 定义：距离 target 还差多少和维护：每选一个数 x，子问题变为 remain - x更新： remain == 0 时收集答案；remain < 0 时剪枝返回 |
start | int | 定义：本轮可选候选的起始下标（含自身） 维护：只从 candidates[start..] 中选，保证组合不重复（如不会出现 [3,2,2] 与 [2,2,3]）更新：选 candidates[i] 后递归传 i（非 i+1），允许同一数重复使用 |
ans | list<list<int>> | 定义：所有和为 target 的不同组合维护：仅当 remain == 0 时将 path 的副本加入更新：每到达合法叶子追加一次；中途不收集半成品 |
落码步骤
1. 初始化结果 ans，可选对 candidates 排序以便剪枝
2. 定义 DFS backtrack(start, remain, path)：若 remain == 0，将 path[:] 加入 ans 并返回；若 remain < 0 则剪枝返回
3. 对 i 从 start 到 len(candidates)-1：若 candidates[i] > remain 可 break（已排序时）
4. 将 candidates[i] 追加到 path，递归 backtrack(i, remain - candidates[i], path)（传 i 允许重复选）
5. 回溯：从 path 弹出末尾元素，继续尝试下一个 i
6. 从 backtrack(0, target, []) 启动，返回 ans
代码实现
class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
ans: list[list[int]] = []
candidates.sort()
def backtrack(start: int, remain: int, path: list[int]) -> None:
if remain == 0:
ans.append(path[:])
return
if remain < 0:
return
for i in range(start, len(candidates)):
if candidates[i] > remain:
break
path.append(candidates[i])
backtrack(i, remain - candidates[i], path)
path.pop()
backtrack(0, target, [])
return ansclass Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> path;
sort(candidates.begin(), candidates.end());
function<void(int, int)> dfs = [&](int start, int remain) {
if (remain == 0) {
ans.push_back(path);
return;
}
if (remain < 0) return;
for (int i = start; i < (int)candidates.size(); i++) {
if (candidates[i] > remain) break;
path.push_back(candidates[i]);
dfs(i, remain - candidates[i]);
path.pop_back();
}
};
dfs(0, target);
return ans;
}
};
// 时间 O(N^(T/min))，空间 O(T/min) 递归栈复杂度分析
O(N^(T/min))（N 为候选数，T 为 target，min 为最小候选值；剪枝后远好于全枚举）
O(T/min)（递归栈深度，不计输出）
常见坑
递归下标传 i+1：本题允许同一数重复使用，必须传 i；传 i+1 会漏解（如 [2,2,3]）。
组合去重失败：若每层从 0 开始选会产生 [2,3] 与 [3,2] 重复，必须用 start 限制只往后选。
收集答案时未拷贝 path：应 ans.append(path[:]) 或 C++ 中在 remain==0 时 push 当前 path 副本，否则后续修改会污染已收集结果。
必测边界 Case
candidates = [2], target = 1 → []（最小候选 2 已大于 target）
candidates = [7], target = 7 → [[7]]
candidates = [2,3,5], target = 8 → 含 [2,2,2,2]
[2,3,6,7], target=7 → [[2,2,3],[7]]，恰好两组
排序不影响正确性，但有助于 remain 剪枝