示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本篇技术指南以 doocs/leetcode 仓库中 0039.Combination Sum 的官方题解文档为骨架系统讲解「组合总和」这道经典回溯题的核心考点如何通过排序 剪枝避免重复组合、控制搜索规模并给出「多叉循环枚举」与「选/不选二叉展开」两种等价写法覆盖 Python3、Java、C、Go、TypeScript、Rust、C#、PHP 共 8 种语言的完整实现。读完本文你将掌握组合类回溯问题的通用模板、两种剪枝策略的适用场景以及如何将该思路迁移到组合总和 II、组合、组合总和 III 等同类题目。题目背景与核心考点题目描述给你一个无重复元素的整数数组candidates和一个目标整数target找出candidates中可以使数字和为目标数target的所有不同组合并以列表形式返回。组合可以按任意顺序返回。两个关键约束决定了本题的解法走向candidates中的同一个数字可以无限制重复被选取只要两个组合中至少有一个数字的被选数量不同就视为不同组合组合与顺序无关。题目保证对于给定的输入和为target的不同组合数少于150个。示例示例 1输入candidates [2,3,6,7], target 7 输出[[2,2,3],[7]] 解释 2 和 3 可以形成一组候选2 2 3 7。注意 2 可以使用多次。 7 也是一个候选7 7。 仅有这两种组合。示例 2输入: candidates [2,3,5], target 8 输出: [[2,2,2,2],[2,3,3],[3,5]]示例 3输入: candidates [2], target 1 输出: []数据范围提示参数范围candidates.length1 candidates.length 30candidates[i]2 candidates[i] 40candidates元素所有元素互不相同target1 target 40从数据范围可以看到n 30、target 40元素最小值为 2因此每个组合的长度理论上限为target / 2 20。虽然理论上搜索空间巨大但得益于剪枝与题目「组合数少于 150」的保证回溯算法可以高效求解。思路分析为什么朴素枚举不可行组合与顺序无关枚举排列会产生重复如果直接对每个数做「无限次选用或不选」的枚举会搜出大量和超过target的路径并且同一组数多重集会因排列顺序不同而被当成不同组合重复统计。例如[2,2,3]和[2,3,2]本质是同一个组合。排序 单向索引天然去重解决方案是先对candidates排序搜索时只从当前下标向右选取。这样同一组数只会以单调不减的顺序被生成一次从根源上避免排列重复排序后数组具有单调性若剩余值s已经小于candidates[i]那么下标i及其后的所有元素都大于s整支搜索树可以立即终止这就是剪枝的数学基础。这也是 doocs/leetcode 该题文档中「方法一排序 剪枝 回溯」的设计起点。方法一排序 剪枝 回溯多叉搜索树算法设计设计函数dfs(i, s)含义为从下标i开始搜索剩余目标值为s。其中i和s都是非负整数当前搜索路径为t最终答案为ans。函数内部逻辑若s 0说明当前路径t的数字和恰好等于target将t的拷贝加入答案ans并返回若s candidates[i]说明当前及后续下标元素都大于剩余目标值路径不合法直接返回剪枝否则枚举j范围j ∈ [i, n)n为数组长度将candidates[j]加入路径t递归调用dfs(j, s - candidates[j])——注意递归起点仍是j而不是j 1这正是「同一个数字可以无限制重复被选取」的体现递归返回后从t中移除该元素回溯恢复现场。主函数中只需调用dfs(0, target)即可得到完整答案。剪枝的正确性「排序 剪枝」的组合是本题性能的关键剪枝条件s candidates[i]由于数组已升序排列一旦剩余目标小于当前元素后续元素只会更大该分支不可能再凑出和为target的组合整支可以直接放弃递归起点保持为j既允许当前数字被反复使用又因为枚举从i起步、不回头杜绝了顺序不同的重复组合。复杂度分析时间复杂度O(2^n × n)其中n为数组candidates的长度。由于剪枝的存在实际运行时间远小于O(2^n × n)空间复杂度O(n)主要开销为递归调用栈深度与路径数组t。多语言实现以下是 doocs/leetcode 仓库该题文档中方法一的完整代码Python3class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: def dfs(i: int, s: int): if s 0: ans.append(t[:]) return if s candidates[i]: return for j in range(i, len(candidates)): t.append(candidates[j]) dfs(j, s - candidates[j]) t.pop() candidates.sort() t [] ans [] dfs(0, target) return ansJavaclass Solution { private ListListInteger ans new ArrayList(); private ListInteger t new ArrayList(); private int[] candidates; public ListListInteger combinationSum(int[] candidates, int target) { Arrays.sort(candidates); this.candidates candidates; dfs(0, target); return ans; } private void dfs(int i, int s) { if (s 0) { ans.add(new ArrayList(t)); return; } if (s candidates[i]) { return; } for (int j i; j candidates.length; j) { t.add(candidates[j]); dfs(j, s - candidates[j]); t.remove(t.size() - 1); } } }Cclass Solution { public: vectorvectorint combinationSum(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); vectorvectorint ans; vectorint t; functionvoid(int, int) dfs { if (s 0) { ans.emplace_back(t); return; } if (s candidates[i]) { return; } for (int j i; j candidates.size(); j) { t.push_back(candidates[j]); dfs(j, s - candidates[j]); t.pop_back(); } }; dfs(0, target); return ans; } };Gofunc combinationSum(candidates []int, target int) (ans [][]int) { sort.Ints(candidates) t : []int{} var dfs func(i, s int) dfs func(i, s int) { if s 0 { ans append(ans, slices.Clone(t)) return } if s candidates[i] { return } for j : i; j len(candidates); j { t append(t, candidates[j]) dfs(j, s-candidates[j]) t t[:len(t)-1] } } dfs(0, target) return }TypeScriptfunction combinationSum(candidates: number[], target: number): number[][] { candidates.sort((a, b) a - b); const ans: number[][] []; const t: number[] []; const dfs (i: number, s: number) { if (s 0) { ans.push(t.slice()); return; } if (s candidates[i]) { return; } for (let j i; j candidates.length; j) { t.push(candidates[j]); dfs(j, s - candidates[j]); t.pop(); } }; dfs(0, target); return ans; }Rustimpl Solution { fn dfs(i: usize, s: i32, candidates: Veci32, t: mut Veci32, ans: mut VecVeci32) { if s 0 { ans.push(t.clone()); return; } if s candidates[i] { return; } for j in i..candidates.len() { t.push(candidates[j]); Self::dfs(j, s - candidates[j], candidates, t, ans); t.pop(); } } pub fn combination_sum(mut candidates: Veci32, target: i32) - VecVeci32 { candidates.sort(); let mut ans Vec::new(); Self::dfs(0, target, candidates, mut vec![], mut ans); ans } }C#public class Solution { private ListIListint ans new ListIListint(); private Listint t new Listint(); private int[] candidates; public IListIListint CombinationSum(int[] candidates, int target) { Array.Sort(candidates); this.candidates candidates; dfs(0, target); return ans; } private void dfs(int i, int s) { if (s 0) { ans.Add(new Listint(t)); return; } if (s candidates[i]) { return; } for (int j i; j candidates.Length; j) { t.Add(candidates[j]); dfs(j, s - candidates[j]); t.RemoveAt(t.Count - 1); } } }仓库源码佐证上述代码与仓库中的独立源码文件一一对应读者可直接对照验证Solution.pyPython 实现核心剪枝条件s candidates[i]与递归dfs(j, s - candidates[j])与文档完全一致Solution.javaJava 实现注意其将candidates排序后存入成员变量dfs通过成员变量访问数组Solution.goGo 实现路径拷贝使用 Go 1.21 标准库slices.Clone(t)避免共享底层数组导致结果被后续回溯污染Solution.rsRust 实现通过t.clone()保存路径快照Solution.tsTypeScript 实现使用t.slice()拷贝路径。一个值得注意的工程细节所有语言在s 0时都必须拷贝路径快照t[:]、new ArrayList(t)、slices.Clone(t)、t.clone()、t.slice()而不能直接加入t本身——因为回溯时会pop修改同一份数组若不拷贝最终ans里的所有组合都会被清空成空数组。方法二排序 剪枝 回溯选/不选二叉展开算法设计方法一用循环枚举「下一个选谁」搜索树是多叉的。方法二把同一算法改写成对当前位置选或不选的二叉树展开设计函数dfs(i, s)含义与之前相同但逻辑改为若s 0将路径t拷贝加入答案ans并返回若i n或者s candidates[i]路径不合法直接返回否则分两种情况不选当前下标元素递归调用dfs(i 1, s)下标前进剩余目标不变选当前下标元素先将candidates[i]加入路径t再递归调用dfs(i, s - candidates[i])下标保持不变以允许该数字被重复选取递归结束后从t中移除回溯。两种写法的搜索树形状不同但产出的答案集合完全相同。方法一适合理解为「横向枚举下一个数字」方法二更贴近「每个位置的决策是拿或不拿」的直觉二者都依赖排序后的s candidates[i]剪枝。多语言实现Python3class Solution: def combinationSum(self, candidates: List[int], target: int) - List[List[int]]: def dfs(i: int, s: int): if s 0: ans.append(t[:]) return if i len(candidates) or s candidates[i]: return dfs(i 1, s) t.append(candidates[i]) dfs(i, s - candidates[i]) t.pop() candidates.sort() t [] ans [] dfs(0, target) return ansJavaclass Solution { private ListListInteger ans new ArrayList(); private ListInteger t new ArrayList(); private int[] candidates; public ListListInteger combinationSum(int[] candidates, int target) { Arrays.sort(candidates); this.candidates candidates; dfs(0, target); return ans; } private void dfs(int i, int s) { if (s 0) { ans.add(new ArrayList(t)); return; } if (i candidates.length || s candidates[i]) { return; } dfs(i 1, s); t.add(candidates[i]); dfs(i, s - candidates[i]); t.remove(t.size() - 1); } }Cclass Solution { public: vectorvectorint combinationSum(vectorint candidates, int target) { sort(candidates.begin(), candidates.end()); vectorvectorint ans; vectorint t; functionvoid(int, int) dfs { if (s 0) { ans.emplace_back(t); return; } if (i candidates.size() || s candidates[i]) { return; } dfs(i 1, s); t.push_back(candidates[i]); dfs(i, s - candidates[i]); t.pop_back(); }; dfs(0, target); return ans; } };Gofunc combinationSum(candidates []int, target int) (ans [][]int) { sort.Ints(candidates) t : []int{} var dfs func(i, s int) dfs func(i, s int) { if s 0 { ans append(ans, slices.Clone(t)) return } if i len(candidates) || s candidates[i] { return } dfs(i1, s) t append(t, candidates[i]) dfs(i, s-candidates[i]) t t[:len(t)-1] } dfs(0, target) return }TypeScriptfunction combinationSum(candidates: number[], target: number): number[][] { candidates.sort((a, b) a - b); const ans: number[][] []; const t: number[] []; const dfs (i: number, s: number) { if (s 0) { ans.push(t.slice()); return; } if (i candidates.length || s candidates[i]) { return; } dfs(i 1, s); t.push(candidates[i]); dfs(i, s - candidates[i]); t.pop(); }; dfs(0, target); return ans; }Rustimpl Solution { fn dfs(i: usize, s: i32, candidates: Veci32, t: mut Veci32, ans: mut VecVeci32) { if s 0 { ans.push(t.clone()); return; } if i candidates.len() || s candidates[i] { return; } Self::dfs(i 1, s, candidates, t, ans); t.push(candidates[i]); Self::dfs(i, s - candidates[i], candidates, t, ans); t.pop(); } pub fn combination_sum(mut candidates: Veci32, target: i32) - VecVeci32 { candidates.sort(); let mut ans Vec::new(); Self::dfs(0, target, candidates, mut vec![], mut ans); ans } }C#public class Solution { private ListIListint ans new ListIListint(); private Listint t new Listint(); private int[] candidates; public IListIListint CombinationSum(int[] candidates, int target) { Array.Sort(candidates); this.candidates candidates; dfs(0, target); return ans; } private void dfs(int i, int s) { if (s 0) { ans.Add(new Listint(t)); return; } if (i candidates.Length || s candidates[i]) { return; } dfs(i 1, s); t.Add(candidates[i]); dfs(i, s - candidates[i]); t.RemoveAt(t.Count - 1); } }PHPclass Solution { /** * param integer[] $candidates * param integer $target * return integer[][] */ function combinationSum($candidates, $target) { $result []; $currentCombination []; $startIndex 0; sort($candidates); $this-findCombinations($candidates, $target, $startIndex, $currentCombination, $result); return $result; } function findCombinations($candidates, $target, $startIndex, $currentCombination, $result) { if ($target 0) { $result[] $currentCombination; return; } for ($i $startIndex; $i count($candidates); $i) { $num $candidates[$i]; if ($num $target) { break; } $currentCombination[] $num; $this-findCombinations($candidates, $target - $num, $i, $currentCombination, $result); array_pop($currentCombination); } } }仓库源码佐证方法二同样有独立源码文件对应Solution2.pyPython 实现「不选」调用dfs(i 1, s)「选」调用dfs(i, s - candidates[i])目录中同时提供了 Solution2.cpp、Solution2.cs、Solution2.go、Solution2.rs、Solution2.ts 等文件与文档中方法二各语言代码一一对应。值得一提的是 Solution.phpPHP 版本属于方法一的变体它把剪枝条件移到了循环内部——当$num $target时直接break。由于数组已排序一旦遇到大于剩余目标的数字后续元素必然更大break与文档中「整支停止」的s candidates[i]剪枝在效果上完全等价可作为理解剪枝本质的补充样例。复杂度分析与方法一相同时间复杂度O(2^n × n)剪枝后实际远小于该上界空间复杂度O(n)。两种写法的对比与选择维度方法一多叉循环方法二选/不选二叉搜索树形状多叉树循环枚举「下一个选谁」二叉树每层决策「拿 or 不拿」递归起点dfs(j, s - candidates[j])允许重复选j「选」分支dfs(i, s - candidates[i])保持下标「不选」分支dfs(i 1, s)剪枝条件s candidates[i]i n或s candidates[i]适用直觉面向「候选序列」逐个追加面向「每个位置取舍」的决策树结果等价性两者答案完全相同两者答案完全相同从源码结构看doocs/leetcode 对这类回溯题普遍采用「两种写法并列」的组织方式方便读者在不同思维模型间切换也便于在相似题目如组合总和 II 中需要跳过重复值中直接复用对应模板。边界情况与正确性验证target小于最小元素示例 3candidates [2], target 1排序后dfs(0, 1)命中s candidates[0]即1 2立即返回输出[]无多余搜索target恰等于某个元素如示例 1 中的[7]在dfs枚举到candidates[2] 7时递归进入dfs(2, 0)命中s 0收集答案元素可无限复用如示例 2 中[2,2,2,2]依赖「选」分支下标不前进方法二或递归起点保持j方法一同一个 2 被连续选取四次去重排序保证生成序列单调不减[2,3,3]只会出现一次[3,2,3]等排列永远不会被生成。相似题目拓展组合总和是「组合类回溯」的题源doocs/leetcode 仓库中收录了直接相关的进阶题建议按以下顺序练习40. 组合总和 II在本题基础上candidates含有重复元素且每个数字只能使用一次解法在排序后还需在同一层跳过与前一个相同的值并改用dfs(j 1, ...)防止复用77. 组合不要求求和只求[1, n]中所有k个数的组合是组合回溯的最简模板216. 组合总和 III限定只用1~9且每个数字只能用一次同时约束组合长度与总和是本题「重复选取」约束的反向变体。通过对比这四道题可以清晰看到是否允许重复选取、数组本身是否含重复值、是否限制组合长度三个维度分别决定了递归起点是j还是j 1、是否需要同层去重、以及是否增加长度剪枝——这正是回溯组合题的完整知识脉络。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐MAS 激活完全指南10 分钟免费搞定 Windows 与 Office 激活MAS 激活完全指南10 分钟免费搞定 Windows 与 Office 激活 打开弹窗就头疼MAS 帮你一次激活 Windows 和 Office Win运维LeetCode 40 Combination Sum II组合总和 II全解法剖析排序去重回溯、频次映射与剪枝优化LeetCode 40 Combination Sum II组合总和 II全解法剖析排序去重回溯、频次映射与剪枝优化 导读 本文以仓库 articles/示例工程LeetCode-Go 题解剖析第 39 题 Combination Sum 回溯求解与剪枝优化LeetCode Go 题解剖析第 39 题 Combination Sum 回溯求解与剪枝优化 本篇技术指南围绕 LeetCode Go 仓库中 第 39示例工程上一篇Windows开发者必备如何用nvm-windows轻松管理Node.js版本下一篇如何快速整理Steam游戏库终极自动分类工具指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考