凡科网站建设推广应用商店下载安装app
第七章 回溯算法
- 77.组合
- 代码随想录文章详解
- 总结
77.组合
以n=5,k=3为例
(1)for循环遍历，递归选择符合要求的值加入path，len(path)==k时，返回
statrtIndex保证每次递归取到的值不重复
剪枝：i<=n-(k-len(path))+1 后续需要k-len(path)个值，因为i可选区间左闭右闭，故+1
func combine(n int, k int) [][]int {res := [][]int{}path := []int{}var helper func(n, k, startIndex int)helper = func(n, k, startIndex int) {if len(path) == k {tmp := make([]int, k)copy(tmp, path)res = append(res, tmp)return}for i:= startIndex; i <= n; i++ {path = append(path, i)helper(n, k, i+1)path = path[:len(path) - 1]}}helper(n, k, 1)return res
}
(2)递归枚举每个值，选/不选
若不选当前值，递归下一个值；若选当前值，加入结果集，回溯，保证当前状态不影响下一次递归
func combine(n int, k int) [][]int {res := [][]int{}path := []int{}var helper func(n, k, i int)helper = func(n, k, i int) {if len(path) == k {tmp := make([]int, k)copy(tmp, path)res = append(res, tmp)return}if i > n {return}helper(n, k, i + 1)path = append(path, i)helper(n, k, i + 1)path = path[:len(path) - 1]}helper(n, k, 1)return res
}
代码随想录文章详解
理论基础
77.组合
总结
循环嵌入递归，循序渐进。感谢代码随想录训练营。