题目

leetcode:216

代码与解析

https://blog.devilwst.top/2021/12/27/组合-回溯算法/
和这道题差不多,只不过这道题的横向长度是确定的,就是9,树的宽度就是9(暂不考虑剪枝)

回溯三部曲:

  • 确定参数及返回值
    传入startIndex, 记录下一次搜索的起始位置

  • 确定终止条件
    和为n, k个数,其实终止条件就可以写出来了,
    只要path里的个数大小等于k,再判断和的大小

if len(path) == k{
    if sum(path)==n{
        tmp := make([]int, k)
        copy(tmp, path)
        res = append(res, tmp)
    }
    return
}
  • 确定单层逻辑
    依然按照回溯的大框架写,
    for循环固定1-9,横向遍历,里面加上递归,回溯。
    i<=9-(k-len(path))+1这里有一个剪枝的操作。
    https://blog.devilwst.top/2021/12/27/组合-回溯算法/我这篇文章说的一样。
    整体代码:
func combinationSum3(k int, n int) [][]int {
    res := [][]int{}
    path := []int{}
    var backtracking func(start int)
    backtracking = func(start int){
        if len(path) == k{
            if sum(path)==n{
                tmp := make([]int, k)
                copy(tmp, path)
                res = append(res, tmp)
            }
            return
        }
        for i := start;i<=9-(k-len(path))+1;i++{
            path = append(path, i)
            backtracking(i+1)
            path = path[:len(path)-1]
        }
    }
    backtracking(1)
    return res
}
func sum(array []int)int{
    res := 0
    for _,v := range array{
        res += v
    }
    return res
}
分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:72522 人次

浙公网安备33011302000604

辽ICP备20003309号