题目

leetcode:216

代码与解析

http://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这里有一个剪枝的操作。
  和http://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
}