题目

leetcode:77

代码与解析

引用一下carl大佬的视频:
https://www.bilibili.com/video/BV1cy4y167mM回溯算法理论篇

https://www.bilibili.com/video/BV1wi4y157e回溯算法代码解析

https://www.bilibili.com/video/BV1wrtyi4y回溯算法剪枝
回溯法三部曲:

  • 确定参数及返回值
    要传入start来记录下一层递归搜索的起始位置,path来记录符合条件的单一结果,不过不是必须的。

  • 确定终止条件
    如果path长度等于k,说明满足条件,要把他转移到res, <注意这里必须要拷贝,不然path是一个指针,res里面的 结果将都是最后一个结果>例如这样

if len(path)==k{
    tmp := make([]int, k)
    copy(tmp, path)
    res = append(res, tmp)
    return
}
  • 确定单层逻辑
    for循环做横向遍历, 递归做纵向遍历,另外别忘了加上回溯
for i:=start;i<=n;i++{
    path = append(path, i)
    // 注意是i+1而不是start+1
    backtracing(i+1, path)
    path = path[:len(path)-1]
}

这里可以进行一个剪枝, 将哪些为空,或者不符合条件的 枝减去。
k-len(path)还剩这么多需要选取,n-(k-len(path))+1:这个表示至多要搜索的位置
具体讲解见carl大佬的视频:
https://www.bilibili.com/回溯剪枝:时间:8:28秒详解

for i:=start;i<=n-(k-len(path))+1;i++{
    path = append(path, i)
    // 注意是i+1而不是start+1
    backtracing(i+1)
    path = path[:len(path)-1]
}

完整代码:

func combine(n int, k int) [][]int {
    res := [][]int{}
    // path := []int{}
    var backtracing func (start int, path []int)
    backtracing = func (start int, path []int){
        if len(path)==k{
            tmp := make([]int, k)
            copy(tmp, path)
            res = append(res, tmp)
            return
        }
        for i:=start;i<=n-(k-len(path))+1;i++{
            path = append(path, i)
            // 注意是i+1而不是start+1
            backtracing(i+1, path)
            path = path[:len(path)-1]
        }

    }
    backtracing(1, []int{})
    return res
}
-----------------------精简版---------------------------
func combine(n int, k int) [][]int {
    res := [][]int{}
    var backtrack func(int, []int)
    backtrack = func(idx int, nums []int) {
        if len(nums) == k {
            t := make([]int, k)
            copy(t, nums)
            res = append(res, t)
            return
        }
        for i := idx; i <= n; i++ {
            backtrack(i + 1, append(nums, i))
        }
    }

    backtrack(1, []int{})
    return res
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:852 天
  • 访问总数:460592 人次
ICP备案号: 辽ICP备20003309号