尧图网站建设 
LeetCode 77 Combinations 组合求解LeetCode-Go 仓库 DFS 剪枝解法全解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 77 题 Combinations组合展开以 LeetCode-Go 仓库中 leetcode/0077.Combinations 的官方题解为核心完整讲解题目含义、DFS深度优先搜索递归思路、剪枝优化的数学依据以及仓库中对应的 Go 实现与单元测试。读完本文你将掌握从 1..n 中选出 k 个数的所有组合这一类回溯问题的标准写法并能举一反三理解仓库中 Permutations排列、Subsets子集、Combination Sum组合总和等同类回溯题解的共同模板。题目回顾从 1..n 中选 k 个数的所有组合题目原文Given two integersnandk, return all possible combinations ofknumbers out of 1 ...n.即给定两个整数n和k返回 1 ... n 中所有可能的k个数的组合。注意组合与排列的区别组合不关心元素内部的顺序[1,2]与[2,1]视为同一个结果因此输出中只出现一次。题目给出的示例n 4, k 2期望输出Input: n 4, k 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]从示例可以看到输出共 6 种组合即数学上的 C(4, 2) 6与组合数公式完全吻合。这也是验证解法正确性的第一道关口任何解法产出的结果数量都应当恰好等于 C(n, k)。解题思路DFS 深搜 剪枝仓库 README 中给出的解题思路非常精炼计算排列组合中的组合用 DFS 深搜即可注意剪枝。其中剪枝是本题性能的关键。所谓剪枝就是在递归过程中提前放弃不可能产生合法结果的搜索分支从而大幅减少递归调用次数。DFS 的搜索树是一棵选与不选的决策树如果不加任何限制组合搜索空间是 2^n 级别的通过控制每层递归的可选起始位置并利用当前层最多还能取多少个数收紧循环上界就能让搜索树只覆盖真正合法的路径。仓库源码逐行拆解LeetCode-Go 仓库为本题提供了完整实现见 77. Combinations.go分为对外入口combine与递归核心generateCombinations两部分。入口函数 combine参数合法性与结果容器初始化func combine(n int, k int) [][]int { if n 0 || k 0 || k n { return [][]int{} } c, res : []int{}, [][]int{} generateCombinations(n, k, 1, c, res) return res }入口函数做了三件事边界校验当n 0、k 0或k n要求的组合长度超过可选数字范围时直接返回空结果[][]int{}。这一防御性判断保证后续递归不会处理非法输入。初始化容器c是当前正在构造的一条组合路径切片res是最终结果集。启动递归调用generateCombinations起始位置start从1开始因为可选数字范围是 1 ... n。递归核心 generateCombinations终止条件与剪枝上界func generateCombinations(n, k, start int, c []int, res *[][]int) { if len(c) k { b : make([]int, len(c)) copy(b, c) *res append(*res, b) return } // i will at most be n - (k - c.size()) 1 for i : start; i n-(k-len(c))1; i { c append(c, i) generateCombinations(n, k, i1, c, res) c c[:len(c)-1] } return }这段代码是整道题的核心包含三个关键设计1. 终止条件叶子节点收集当len(c) k时说明当前路径已经收集满 k 个数构成一个合法组合。此时必须make一个新的切片b并copy再把b追加进*res。这一步拷贝副本至关重要因为c是递归中共享复用的切片后续回溯c c[:len(c)-1]会修改底层数组若不拷贝最终res里存的所有组合都会指向同一块被反复改写的内存导致结果全部相同。2. 剪枝上界核心优化循环条件i n-(k-len(c))1是本题剪枝的数学表达。推导逻辑如下当前路径c已有len(c)个元素距离目标还差k - len(c)个为了让剩余位置能被填满当前选择的i后面含i本身至少要剩下k - len(c)个数可选因此i的最大值不能超过n - (k - len(c)) 1一旦超过即使把后面所有数字都选上也凑不满 k 个这条分支必然失败应当剪掉。例如n 4, k 2当c为空时i 4 - (2-0) 1 3所以第一层只会尝试i 1, 2, 3i 4被剪掉——因为选了 4 之后后面没有数字可配成第二个元素。这正是剪枝消除无效递归的具体体现。3. 回溯撤销选择递归返回后执行c c[:len(c)-1]把刚才加入的i弹出恢复路径状态继续尝试下一个i。这是所有回溯算法的标准撤销动作配合start i1的传参保证组合内数字严格递增天然去重不会产生[1,2]与[2,1]这类重复结果。递归过程可视化n 4, k 2以题目示例模拟执行过程第一层start 1循环i 1, 2, 34 被剪枝当i 1时c [1]递归进入第二层start 2循环i 2, 3, 4分别得到[1,2]、[1,3]、[1,4]三个组合并收集回溯弹出1i 2时得到[2,3]、[2,4]i 3时得到[3,4]。最终收集到 6 个组合与题目示例一致。复杂度分析时间复杂度需要枚举 C(n, k) 个组合每个组合构造一次路径总时间复杂度为 O(C(n, k) × k)。剪枝不改变渐进复杂度但显著减少实际递归次数。空间复杂度递归深度最大为 k路径切片c长度为 k额外空间为 O(k)不含存储结果所需的空间。单元测试与运行验证仓库为本题编写了完整的单元测试见 77. Combinations_test.go覆盖两组用例标准用例n 4, k 2期望输出与题目示例完全一致边界用例n 0, k 0期望输出空结果[][]int{}用于验证入口函数的防御性判断。测试采用参数-答案配对的结构化写法para77封装输入参数ans77封装期望答案question77将二者绑定最后在Test_Problem77中循环断言combine(p.n, p.k)的输出。在仓库根目录可以运行测试验证gotest.sh脚本中定义了整个 leetcode 包的覆盖率测试方式# 单独跑本题测试 go test -v -run Test_Problem77 ./leetcode/0077.Combinations/ # 跑整个仓库并生成覆盖率 ./gotest.sh触类旁通仓库中的回溯算法家族Combinations 是回溯算法中组合类问题的代表LeetCode-Go 仓库中还有大量同源问题可以对照学习它们的模板高度一致——DFS 递归 路径记录 剪枝/去重题目仓库路径与 77 题的差异46. Permutationsleetcode/0046.Permutations全排列引入used布尔数组标记已选元素长度到达len(nums)即收集47. Permutations IIleetcode/0047.Permutations-II含重复元素的全排列在 46 基础上增加去重逻辑78. Subsetsleetcode/0078.Subsets子集问题外层按 k 0..n 分别调用组合生成等价于任意长度的组合90. Subsets IIleetcode/0090.Subsets-II含重复元素的子集需先排序再去重39. Combination Sumleetcode/0039.Combination-Sum目标值求和元素可重复使用递归时index保持不变并配合nums[i] target剪枝216. Combination Sum IIIleetcode/0216.Combination-Sum-III在 1..9 中选 k 个数和为 n把 77 的长度约束与 39 的和约束结合以 216. Combination Sum III 为例可以看到它与 77 题几乎同构同样是start从 1 开始、i1递进、c c[:len(c)-1]回溯只是终止条件从长度等于 k变成了目标和归零且长度等于 k。对比 78. Subsets 的generateSubsets还能发现一个规律77 题剪枝上界i n-(k-len(c))1在子集问题中对应i len(nums)-(k-len(c))1本质是同一套剩余可填位的数学约束只是数组下标从 0 开始而已。理解了 77 题的剪枝整套回溯家族的核心逻辑就都通了。小结LeetCode 77 题 Combinations 是回溯算法最经典的入门题之一。LeetCode-Go 仓库给出的 Go 实现77. Combinations.go通过三个要点解决了问题DFS 深搜递归逐层选择数字start递增保证组合内元素有序、不重不漏剪枝优化用i n-(k-len(c))1收紧循环上界剪掉填不满 k 个数的无效分支路径拷贝收集结果时复制切片副本避免共享底层数组导致的互相覆盖。配合仓库中完整的单元测试77. Combinations_test.go这套解法可以直接复制运行验证。掌握本题后再对照 46、47、78、90、39、216 等同类题目即可系统化地建立回溯算法的问题解决框架。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 77 Combinations 组合求解：LeetCode-Go 仓库 DFS 剪枝解法全解析
LeetCode 77 Combinations 组合求解LeetCode-Go 仓库 DFS 剪枝解法全解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 77 题 Combinations组合展开以 LeetCode-Go 仓库中 leetcode/0077.Combinations 的官方题解为核心完整讲解题目含义、DFS深度优先搜索递归思路、剪枝优化的数学依据以及仓库中对应的 Go 实现与单元测试。读完本文你将掌握从 1..n 中选出 k 个数的所有组合这一类回溯问题的标准写法并能举一反三理解仓库中 Permutations排列、Subsets子集、Combination Sum组合总和等同类回溯题解的共同模板。题目回顾从 1..n 中选 k 个数的所有组合题目原文Given two integersnandk, return all possible combinations ofknumbers out of 1 ...n.即给定两个整数n和k返回 1 ... n 中所有可能的k个数的组合。注意组合与排列的区别组合不关心元素内部的顺序[1,2]与[2,1]视为同一个结果因此输出中只出现一次。题目给出的示例n 4, k 2期望输出Input: n 4, k 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]从示例可以看到输出共 6 种组合即数学上的 C(4, 2) 6与组合数公式完全吻合。这也是验证解法正确性的第一道关口任何解法产出的结果数量都应当恰好等于 C(n, k)。解题思路DFS 深搜 剪枝仓库 README 中给出的解题思路非常精炼计算排列组合中的组合用 DFS 深搜即可注意剪枝。其中剪枝是本题性能的关键。所谓剪枝就是在递归过程中提前放弃不可能产生合法结果的搜索分支从而大幅减少递归调用次数。DFS 的搜索树是一棵选与不选的决策树如果不加任何限制组合搜索空间是 2^n 级别的通过控制每层递归的可选起始位置并利用当前层最多还能取多少个数收紧循环上界就能让搜索树只覆盖真正合法的路径。仓库源码逐行拆解LeetCode-Go 仓库为本题提供了完整实现见 77. Combinations.go分为对外入口combine与递归核心generateCombinations两部分。入口函数 combine参数合法性与结果容器初始化func combine(n int, k int) [][]int { if n 0 || k 0 || k n { return [][]int{} } c, res : []int{}, [][]int{} generateCombinations(n, k, 1, c, res) return res }入口函数做了三件事边界校验当n 0、k 0或k n要求的组合长度超过可选数字范围时直接返回空结果[][]int{}。这一防御性判断保证后续递归不会处理非法输入。初始化容器c是当前正在构造的一条组合路径切片res是最终结果集。启动递归调用generateCombinations起始位置start从1开始因为可选数字范围是 1 ... n。递归核心 generateCombinations终止条件与剪枝上界func generateCombinations(n, k, start int, c []int, res *[][]int) { if len(c) k { b : make([]int, len(c)) copy(b, c) *res append(*res, b) return } // i will at most be n - (k - c.size()) 1 for i : start; i n-(k-len(c))1; i { c append(c, i) generateCombinations(n, k, i1, c, res) c c[:len(c)-1] } return }这段代码是整道题的核心包含三个关键设计1. 终止条件叶子节点收集当len(c) k时说明当前路径已经收集满 k 个数构成一个合法组合。此时必须make一个新的切片b并copy再把b追加进*res。这一步拷贝副本至关重要因为c是递归中共享复用的切片后续回溯c c[:len(c)-1]会修改底层数组若不拷贝最终res里存的所有组合都会指向同一块被反复改写的内存导致结果全部相同。2. 剪枝上界核心优化循环条件i n-(k-len(c))1是本题剪枝的数学表达。推导逻辑如下当前路径c已有len(c)个元素距离目标还差k - len(c)个为了让剩余位置能被填满当前选择的i后面含i本身至少要剩下k - len(c)个数可选因此i的最大值不能超过n - (k - len(c)) 1一旦超过即使把后面所有数字都选上也凑不满 k 个这条分支必然失败应当剪掉。例如n 4, k 2当c为空时i 4 - (2-0) 1 3所以第一层只会尝试i 1, 2, 3i 4被剪掉——因为选了 4 之后后面没有数字可配成第二个元素。这正是剪枝消除无效递归的具体体现。3. 回溯撤销选择递归返回后执行c c[:len(c)-1]把刚才加入的i弹出恢复路径状态继续尝试下一个i。这是所有回溯算法的标准撤销动作配合start i1的传参保证组合内数字严格递增天然去重不会产生[1,2]与[2,1]这类重复结果。递归过程可视化n 4, k 2以题目示例模拟执行过程第一层start 1循环i 1, 2, 34 被剪枝当i 1时c [1]递归进入第二层start 2循环i 2, 3, 4分别得到[1,2]、[1,3]、[1,4]三个组合并收集回溯弹出1i 2时得到[2,3]、[2,4]i 3时得到[3,4]。最终收集到 6 个组合与题目示例一致。复杂度分析时间复杂度需要枚举 C(n, k) 个组合每个组合构造一次路径总时间复杂度为 O(C(n, k) × k)。剪枝不改变渐进复杂度但显著减少实际递归次数。空间复杂度递归深度最大为 k路径切片c长度为 k额外空间为 O(k)不含存储结果所需的空间。单元测试与运行验证仓库为本题编写了完整的单元测试见 77. Combinations_test.go覆盖两组用例标准用例n 4, k 2期望输出与题目示例完全一致边界用例n 0, k 0期望输出空结果[][]int{}用于验证入口函数的防御性判断。测试采用参数-答案配对的结构化写法para77封装输入参数ans77封装期望答案question77将二者绑定最后在Test_Problem77中循环断言combine(p.n, p.k)的输出。在仓库根目录可以运行测试验证gotest.sh脚本中定义了整个 leetcode 包的覆盖率测试方式# 单独跑本题测试 go test -v -run Test_Problem77 ./leetcode/0077.Combinations/ # 跑整个仓库并生成覆盖率 ./gotest.sh触类旁通仓库中的回溯算法家族Combinations 是回溯算法中组合类问题的代表LeetCode-Go 仓库中还有大量同源问题可以对照学习它们的模板高度一致——DFS 递归 路径记录 剪枝/去重题目仓库路径与 77 题的差异46. Permutationsleetcode/0046.Permutations全排列引入used布尔数组标记已选元素长度到达len(nums)即收集47. Permutations IIleetcode/0047.Permutations-II含重复元素的全排列在 46 基础上增加去重逻辑78. Subsetsleetcode/0078.Subsets子集问题外层按 k 0..n 分别调用组合生成等价于任意长度的组合90. Subsets IIleetcode/0090.Subsets-II含重复元素的子集需先排序再去重39. Combination Sumleetcode/0039.Combination-Sum目标值求和元素可重复使用递归时index保持不变并配合nums[i] target剪枝216. Combination Sum IIIleetcode/0216.Combination-Sum-III在 1..9 中选 k 个数和为 n把 77 的长度约束与 39 的和约束结合以 216. Combination Sum III 为例可以看到它与 77 题几乎同构同样是start从 1 开始、i1递进、c c[:len(c)-1]回溯只是终止条件从长度等于 k变成了目标和归零且长度等于 k。对比 78. Subsets 的generateSubsets还能发现一个规律77 题剪枝上界i n-(k-len(c))1在子集问题中对应i len(nums)-(k-len(c))1本质是同一套剩余可填位的数学约束只是数组下标从 0 开始而已。理解了 77 题的剪枝整套回溯家族的核心逻辑就都通了。小结LeetCode 77 题 Combinations 是回溯算法最经典的入门题之一。LeetCode-Go 仓库给出的 Go 实现77. Combinations.go通过三个要点解决了问题DFS 深搜递归逐层选择数字start递增保证组合内元素有序、不重不漏剪枝优化用i n-(k-len(c))1收紧循环上界剪掉填不满 k 个数的无效分支路径拷贝收集结果时复制切片副本避免共享底层数组导致的互相覆盖。配合仓库中完整的单元测试77. Combinations_test.go这套解法可以直接复制运行验证。掌握本题后再对照 46、47、78、90、39、216 等同类题目即可系统化地建立回溯算法的问题解决框架。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考