题目
代码与解析
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
}