LeetCode-Go 题解剖析Combination Sum II 的排序去重与回溯搜索【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中 0040.Combination-Sum-II 题解文档展开讲解组合总和 II这道经典回溯题的完整解法如何在候选数组含重复元素、且每个数字只能使用一次的约束下通过排序 同层剪枝实现去重并用 Go 语言写出可运行的回溯代码。读完后你将掌握该题的 Go 参考实现细节、与第 39 题Combination Sum及第 47 题Permutations II的关键差异以及如何在仓库中通过测试用例验证正确性。题目描述给定一个候选数字集合candidates和一个目标数字target找出candidates中所有元素之和等于target的唯一组合。约束条件来自原题解文档candidates中的每个数字在组合中只能使用一次所有数字包括target均为正整数结果集不能包含重复的组合。示例 1输入: candidates [10,1,2,7,6,1,5], target 8 一个解集是: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]注意输入中有两个1但两个[1, 7]只算一种组合——这正是本题去重要求的核心。示例 2输入: candidates [2,5,2,1,2], target 5 一个解集是: [ [1,2,2], [5] ]数组中有三个2但在解集[1,2,2]中最多只能取两个2因为1225这体现了每个数字只能用一次的约束。解题思路与第 39 题、第 47 题的关系原题解文档给出的解题脉络是本题是第 39 题Combination Sum的加强版第 39 题中元素可以重复利用同一元素可无限次使用本题中元素只能使用有限次数——因为数组存在重复元素且每个元素只能用一次本题的去重手段与第 47 题Permutations II类似都是先排序再在同层循环中跳过相邻重复值。把仓库中两道相关题的源码放在一起对比差异会非常直观。与第 39 题的差异递归起点 i vs i1第 39 题的实现见 39. Combination Sum.go其核心递归是c append(c, nums[i]) findcombinationSum(nums, target-nums[i], i, c, res) // index 依旧不变因为一个元素可以取多次 c c[:len(c)-1]递归传回的起点是i而不是i1允许下一层从当前元素自身开始从而实现同一数字反复选取。而第 40 题必须传i1强制向后移动保证每个下标至多被使用一次。与第 47 题的相似排序 相邻去重第 47 题的实现见 47. Permutations II.go其去重判据是if i 0 nums[i] nums[i-1] !(*used)[i-1] { // 这里是去重的关键逻辑 continue }第 47 题使用used数组标记访问状态同层中前一个相同值尚未使用时跳过当前值。第 40 题由于是只向后枚举的回溯不需要used数组判据简化为更直接的i index nums[i] nums[i-1]但思想完全一致同一决策层中相同的值只允许出现一次。Go 参考实现与逐行解析仓库中的参考实现位于 40. Combination Sum II.go与题解文档中的代码完全一致共两个函数func combinationSum2(candidates []int, target int) [][]int { if len(candidates) 0 { return [][]int{} } c, res : []int{}, [][]int{} sort.Ints(candidates) // 这里是去重的关键逻辑 findcombinationSum2(candidates, target, 0, c, res) return res } func findcombinationSum2(nums []int, target, index int, c []int, res *[][]int) { if target 0 { b : make([]int, len(c)) copy(b, c) *res append(*res, b) return } for i : index; i len(nums); i { if i index nums[i] nums[i-1] { // 这里是去重的关键逻辑,本次不取重复数字下次循环可能会取重复数字 continue } if target nums[i] { c append(c, nums[i]) findcombinationSum2(nums, target-nums[i], i1, c, res) c c[:len(c)-1] } } }入口函数 combinationSum2边界处理candidates为空时直接返回[][]int{}与测试用例{[]int{}, 8} - [][]int{}对应c是当前正在构建的组合路径res是结果集sort.Ints(candidates)是去重的前提只有先排序重复值才会相邻后续nums[i] nums[i-1]的相邻比较才成立结果集通过指针res向下传递避免每层切片复制这也是仓库内 39、47、40 三题统一的写法。递归函数 findcombinationSum2递归终止条件target 0时说明当前路径恰好凑满目标值。注意这里用makecopy把路径c拷贝一份再存入结果集——因为c是会被回溯修改的共享切片直接append(res, c)会把所有解都指向同一块内存。枚举循环是算法主体三个关键点去重判据i index nums[i] nums[i-1]当i index时说明当前元素不是本层循环的第一个选择。如果它与前一个元素相同则跳过——这保证了同一层中相同的值只取第一次。源码注释特别强调本次不取重复数字下次循环可能会取重复数字例如[1, 1, 6]中两个1分属不同递归层第一层取第一个1第二层从下标 1 开始取第二个1仍然合法。剪枝条件target nums[i]所有数字为正整数只有当前值不超过剩余目标值才值得选取。与第 39 题用if nums[i] target { break }排序后遇到超大的值直接结束循环不同这里用if target nums[i]只对本层取值做过滤、不提前break——两种写法功能等价仓库选择了与自身结构更一致的判断形式。回溯三部曲append选值 → 递归i1注意是i1而非i→c c[:len(c)-1]撤销选择。i1这一处就是每个数字只能用一次在代码上的直接体现。测试用例与运行验证仓库为该题提供了标准testing用例位于 40. Combination Sum II_test.go。测试采用仓库统一的question40 { para40; ans40 }结构体组织三组输入qs : []question40{ { para40{[]int{10, 1, 2, 7, 6, 1, 5}, 8}, ans40{[][]int{{1, 7}, {1, 2, 5}, {2, 6}, {1, 1, 6}}}, }, { para40{[]int{2, 5, 2, 1, 2}, 5}, ans40{[][]int{{1, 2, 2}, {5}}}, }, { para40{[]int{}, 8}, ans40{[][]int{}}, }, }三组用例分别覆盖正常含重复元素的输入验证去重、多重复元素且目标值恰等于数组中元素、空输入边界验证返回[][]int{}。每组用例通过combinationSum2(p.n, p.k)调用入口函数并打印输入输出与题解文档中的两个 Example 一一对应。仓库根目录的 go.mod 声明模块为github.com/halfrost/LeetCode-GoGo 版本要求 1.19所有题解位于leetcode/...包下。验证本題解可以通过仓库自带脚本 gotest.sh 对整个leetcode目录跑覆盖率go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以单独针对本题包运行go test ./leetcode/0040.Combination-Sum-II/观察打印的实际组合输出该包内所有题共用package leetcode实际运行时以完整包编译为准。小结本题相对第 39 题的核心变化是递归起点从i变为i1从而把可重复选取收紧为每个下标至多使用一次去重方案继承第 47 题的先排序、同层跳过相邻重复值思想但省去used数组判据简化为i index nums[i] nums[i-1]实现要点排序是去重前提、路径需拷贝后入结果集、i1递归保证元素不重复使用、target nums[i]完成正整数剪枝参考实现与测试分别位于 leetcode/0040.Combination-Sum-II/40. Combination Sum II.go 和 leetcode/0040.Combination-Sum-II/40. Combination Sum II_test.go三组用例覆盖了主流程、重复元素与空输入边界。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/13 11:39:31 · 阅读 1.2k LeetCode-Go 题解剖析：Combination Sum II 的排序去重与回溯搜索
LeetCode-Go 题解剖析Combination Sum II 的排序去重与回溯搜索【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于 LeetCode-Go 仓库中 0040.Combination-Sum-II 题解文档展开讲解组合总和 II这道经典回溯题的完整解法如何在候选数组含重复元素、且每个数字只能使用一次的约束下通过排序 同层剪枝实现去重并用 Go 语言写出可运行的回溯代码。读完后你将掌握该题的 Go 参考实现细节、与第 39 题Combination Sum及第 47 题Permutations II的关键差异以及如何在仓库中通过测试用例验证正确性。题目描述给定一个候选数字集合candidates和一个目标数字target找出candidates中所有元素之和等于target的唯一组合。约束条件来自原题解文档candidates中的每个数字在组合中只能使用一次所有数字包括target均为正整数结果集不能包含重复的组合。示例 1输入: candidates [10,1,2,7,6,1,5], target 8 一个解集是: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]注意输入中有两个1但两个[1, 7]只算一种组合——这正是本题去重要求的核心。示例 2输入: candidates [2,5,2,1,2], target 5 一个解集是: [ [1,2,2], [5] ]数组中有三个2但在解集[1,2,2]中最多只能取两个2因为1225这体现了每个数字只能用一次的约束。解题思路与第 39 题、第 47 题的关系原题解文档给出的解题脉络是本题是第 39 题Combination Sum的加强版第 39 题中元素可以重复利用同一元素可无限次使用本题中元素只能使用有限次数——因为数组存在重复元素且每个元素只能用一次本题的去重手段与第 47 题Permutations II类似都是先排序再在同层循环中跳过相邻重复值。把仓库中两道相关题的源码放在一起对比差异会非常直观。与第 39 题的差异递归起点 i vs i1第 39 题的实现见 39. Combination Sum.go其核心递归是c append(c, nums[i]) findcombinationSum(nums, target-nums[i], i, c, res) // index 依旧不变因为一个元素可以取多次 c c[:len(c)-1]递归传回的起点是i而不是i1允许下一层从当前元素自身开始从而实现同一数字反复选取。而第 40 题必须传i1强制向后移动保证每个下标至多被使用一次。与第 47 题的相似排序 相邻去重第 47 题的实现见 47. Permutations II.go其去重判据是if i 0 nums[i] nums[i-1] !(*used)[i-1] { // 这里是去重的关键逻辑 continue }第 47 题使用used数组标记访问状态同层中前一个相同值尚未使用时跳过当前值。第 40 题由于是只向后枚举的回溯不需要used数组判据简化为更直接的i index nums[i] nums[i-1]但思想完全一致同一决策层中相同的值只允许出现一次。Go 参考实现与逐行解析仓库中的参考实现位于 40. Combination Sum II.go与题解文档中的代码完全一致共两个函数func combinationSum2(candidates []int, target int) [][]int { if len(candidates) 0 { return [][]int{} } c, res : []int{}, [][]int{} sort.Ints(candidates) // 这里是去重的关键逻辑 findcombinationSum2(candidates, target, 0, c, res) return res } func findcombinationSum2(nums []int, target, index int, c []int, res *[][]int) { if target 0 { b : make([]int, len(c)) copy(b, c) *res append(*res, b) return } for i : index; i len(nums); i { if i index nums[i] nums[i-1] { // 这里是去重的关键逻辑,本次不取重复数字下次循环可能会取重复数字 continue } if target nums[i] { c append(c, nums[i]) findcombinationSum2(nums, target-nums[i], i1, c, res) c c[:len(c)-1] } } }入口函数 combinationSum2边界处理candidates为空时直接返回[][]int{}与测试用例{[]int{}, 8} - [][]int{}对应c是当前正在构建的组合路径res是结果集sort.Ints(candidates)是去重的前提只有先排序重复值才会相邻后续nums[i] nums[i-1]的相邻比较才成立结果集通过指针res向下传递避免每层切片复制这也是仓库内 39、47、40 三题统一的写法。递归函数 findcombinationSum2递归终止条件target 0时说明当前路径恰好凑满目标值。注意这里用makecopy把路径c拷贝一份再存入结果集——因为c是会被回溯修改的共享切片直接append(res, c)会把所有解都指向同一块内存。枚举循环是算法主体三个关键点去重判据i index nums[i] nums[i-1]当i index时说明当前元素不是本层循环的第一个选择。如果它与前一个元素相同则跳过——这保证了同一层中相同的值只取第一次。源码注释特别强调本次不取重复数字下次循环可能会取重复数字例如[1, 1, 6]中两个1分属不同递归层第一层取第一个1第二层从下标 1 开始取第二个1仍然合法。剪枝条件target nums[i]所有数字为正整数只有当前值不超过剩余目标值才值得选取。与第 39 题用if nums[i] target { break }排序后遇到超大的值直接结束循环不同这里用if target nums[i]只对本层取值做过滤、不提前break——两种写法功能等价仓库选择了与自身结构更一致的判断形式。回溯三部曲append选值 → 递归i1注意是i1而非i→c c[:len(c)-1]撤销选择。i1这一处就是每个数字只能用一次在代码上的直接体现。测试用例与运行验证仓库为该题提供了标准testing用例位于 40. Combination Sum II_test.go。测试采用仓库统一的question40 { para40; ans40 }结构体组织三组输入qs : []question40{ { para40{[]int{10, 1, 2, 7, 6, 1, 5}, 8}, ans40{[][]int{{1, 7}, {1, 2, 5}, {2, 6}, {1, 1, 6}}}, }, { para40{[]int{2, 5, 2, 1, 2}, 5}, ans40{[][]int{{1, 2, 2}, {5}}}, }, { para40{[]int{}, 8}, ans40{[][]int{}}, }, }三组用例分别覆盖正常含重复元素的输入验证去重、多重复元素且目标值恰等于数组中元素、空输入边界验证返回[][]int{}。每组用例通过combinationSum2(p.n, p.k)调用入口函数并打印输入输出与题解文档中的两个 Example 一一对应。仓库根目录的 go.mod 声明模块为github.com/halfrost/LeetCode-GoGo 版本要求 1.19所有题解位于leetcode/...包下。验证本題解可以通过仓库自带脚本 gotest.sh 对整个leetcode目录跑覆盖率go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...也可以单独针对本题包运行go test ./leetcode/0040.Combination-Sum-II/观察打印的实际组合输出该包内所有题共用package leetcode实际运行时以完整包编译为准。小结本题相对第 39 题的核心变化是递归起点从i变为i1从而把可重复选取收紧为每个下标至多使用一次去重方案继承第 47 题的先排序、同层跳过相邻重复值思想但省去used数组判据简化为i index nums[i] nums[i-1]实现要点排序是去重前提、路径需拷贝后入结果集、i1递归保证元素不重复使用、target nums[i]完成正整数剪枝参考实现与测试分别位于 leetcode/0040.Combination-Sum-II/40. Combination Sum II.go 和 leetcode/0040.Combination-Sum-II/40. Combination Sum II_test.go三组用例覆盖了主流程、重复元素与空输入边界。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考