LeetCode-Go 第 40 题实战：Combination Sum II 的 Go 回溯解法与排序去重关键逻辑

LeetCode-Go 第 40 题实战Combination Sum II 的 Go 回溯解法与排序去重关键逻辑【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中 第 40 题 Combination Sum II 的题解文档 展开完整讲解这道组合总和 II题的题目要求、输入输出样例与解题思路并结合仓库中的 Go 源码 40. Combination Sum II.go 深入剖析排序 回溯去重的核心实现最后覆盖 测试文件 中全部用例的验证方式。读完本文你将掌握带重复元素的组合枚举如何做同层去重、与第 39 题元素可无限次使用和与第 47 题全排列去重的差异在哪、以及如何在本地运行验证。题目要求给定一个候选数字集合candidates和一个目标数target找出candidates中所有可以使数字和为target的组合。核心约束有两条每个数字在每个组合中只能使用一次。这一点与第 39 题Combination Sum形成对比——第 39 题中同一元素可以被无限制重复选取而本题中重复元素也只能按其在原数组中出现的次数有限次使用所有数字包括target都是正整数解集不能包含重复的组合即如果candidates中存在重复元素最终输出中相同的组合只允许出现一次。输入输出示例原始题解文档给出了两个标准示例可直接作为手工验证的基准示例 1Input: candidates [10,1,2,7,6,1,5], target 8 A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]注意candidates中有两个1所以[1, 1, 6]是合法组合如果数组里只有一个1这个组合就不应出现——这正是每个数字只能用一次约束的体现。示例 2Input: candidates [2,5,2,1,2], target 5 A solution set is: [ [1,2,2], [5] ]candidates中有三个2但[2,2,...]相关的组合中2最多只能取三个本题解集中恰好[1,2,2]用到了其中两个。解题思路第 39 题的加强版题解文档leetcode/0040.Combination-Sum-II/README.md给出的思路要点是题目要求和为target的所有组合且组合需要去重。这一题是 第 39 题 的加强版第 39 题元素可以重复利用重复元素可无限次使用本题中元素只能有限次数使用——因为存在重复元素且每个元素只能用一次重复元素只能使用有限次这一题和 第 47 题 类似两者的共同点都是数组含重复元素、结果需要去重去重手段也都是先排序再在搜索时做判断。下面结合仓库源码把这条思路落到实现上。Go 实现解析完整源码见 leetcode/0040.Combination-Sum-II/40. Combination Sum II.go整体结构是入口函数 DFS 递归函数两段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] } } }几个关键点逐一说明入口先判空candidates为空时直接返回空的[][]int{}避免空切片上的无意义搜索。这一点在测试用例中也有覆盖见下文测试验证一节的第三个用例[]int{}, 8。sort.Ints(candidates)是去重的前提只有先排序重复元素才会相邻后面nums[i] nums[i-1]的判断才成立。源码注释明确标注这里是去重的关键逻辑。for i : index控制搜索起点index参数保证每一层只向后取数天然避免[1,2]和[2,1]这类顺序不同但本质相同的组合被重复枚举这也是组合问题区别于排列问题的地方。递归终止条件target 0命中目标时先把当前组合c复制一份makecopy再追加进结果。这一步很关键c是回溯过程中共享的切片如果直接append(c)后续回溯会改写它导致结果集里所有组合指向同一块数据。回溯三件套append选数 → 递归 →c c[:len(c)-1]撤销选择标准的回溯模板。核心去重逻辑i index nums[i] nums[i-1]这一行是整道题的题眼源码注释写得很直白本次不取重复数字下次循环可能会取重复数字。它的语义是在同一层递归内相同值的元素只允许被第一个出现的那个代表。举例说明排序后candidates [1, 1, 2, 5, 6, 7, 10]示例 1 排序结果。在某一层的for循环里遍历到第二个1时i index成立且nums[i] nums[i-1]直接continue跳过。这样以1开头的分支只从一个1展开一次就不会产生重复组合。而下次循环可能会取重复数字指的是跳过的限制只作用于当前这一层进入下一层递归后index已经前移两个1都可以被用到例如[1, 1, 6]就是第二层取了第二个1得到的恰好满足每个数字用一次的约束。这个写法和第 47 题的去重写法不同但思想同源。第 47 题的源码 用的是used数组标记if i 0 nums[i] nums[i-1] !(*used)[i-1] { // 这里是去重的关键逻辑 continue }第 47 题是全排列每一层都要遍历全部下标所以用前一个相同元素未被使用则跳过来保证同层去重而第 40 题是组合搜索本身只向后推进因此用i index就能等价表达跳过同层的后续重复元素无需额外的used数组。从源码结构看这是同一套排序后同层剪枝思想在两类搜索形态下的两种落地方式。与第 39 题的两个关键差异对比 第 39 题源码两处差异直接对应题目约束的变化差异点第 39 题元素可重复使用第 40 题元素只能用一次递归时下标findcombinationSum(nums, target-nums[i], i, c, res)index传i不变允许下一层再选同一个元素findcombinationSum2(nums, target-nums[i], i1, c, res)index传i1强制向后推进保证每个元素只取一次重复元素处理输入本身无重复元素无需去重输入可能含重复元素排序后用i index nums[i] nums[i-1]同层剪枝此外第 39 题在循环内有一句if nums[i] target { break }的剪枝排序后一旦超出目标就可以直接终止本层循环第 40 题的源码则采用if target nums[i]的过滤写法——超标的元素只是被跳过而不终止循环因为不要求后面更大的一定都超标的断言虽然排序后同样成立。两种写法功能等价从源码结构看第 40 题的实现更偏保守。测试用例与运行验证测试文件 40. Combination Sum II_test.go 定义了Test_Problem40包含三个用例与文档示例完全对应并补充了边界情况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{}}, }, }第三个用例空输入返回空解集正好验证了入口函数的判空分支。测试以fmt.Printf打印每个用例的输入与combinationSum2(p.n, p.k)的实际输出便于人工比对。运行方式仓库要求 Go 1.19见 go.mod在仓库根目录执行go test ./leetcode/ -run Test_Problem40 -v即可只跑本题用例并查看打印结果也可以用仓库自带的 gotest.sh 对整个leetcode目录跑全量测试并生成coverage.txt该脚本对每个包一次性-coverprofile产出单一合法的覆盖率文件。小结本题是第 39 题的加强版候选数组可含重复元素、每个元素限用一次、解集去重仓库的 Go 解法分两步走sort.Ints排序让重复元素相邻递归循环内用i index nums[i] nums[i-1]在同层跳过重复元素从根源上杜绝重复组合与第 47 题相比组合搜索天然向后推进去重不需要used数组只需跳过同层重复这一条判断递归传i1而非i是实现每个元素只能用一次的唯一改动点也是与第 39 题解法最本质的区别复制当前路径再入结果集、空输入判空、三个覆盖文档示例与边界的测试用例构成了该解法在仓库内 100% 覆盖测试下的可验证闭环。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考