力扣链接:
https://leetcode-cn.com/probl…
解题思路:
- 这道题目的解题思路是回溯算法,回溯算法是有固定的模版套路的,简略来说有以下三个条件:(1)抉择列表,代表门路抉择的时候从哪个列表中抉择数据 (2)门路列表,示意哪些数字曾经被抉择进以后门路 (3)终止条件,示意什么时候完结循环,个别是k个数的时候或者和为target的时候
private void backtrack("原始参数") {
//终止条件(递归必须要有终止条件)
if ("终止条件") {
//一些逻辑操作(可有可无,视状况而定)
return;
}
for (int i = "for循环开始的参数"; i < "for循环完结的参数"; i++) {
//一些逻辑操作(可有可无,视状况而定)
//做出抉择
//递归
backtrack("新的参数");
//一些逻辑操作(可有可无,视状况而定)
//撤销抉择
}
}
伪代码如上所示,在这道题中,有两个完结抉择条件,一个是当门路中的数量等于规定的k个时,另一个是所有的数字和n<=0时;下标从1~9。能够写出代码如下:
func combinationSum3(k int, n int) [][]int {
res := [][]int{}
backtrack(&res, []int{}, k, n , 1)
return res
}
func backtrack(res *[][]int, path []int, k, n, start int) {
if len(path) == k || n <= 0 {
if len(path) == k && n == 0 {
newPath := make([]int, len(path))
copy(newPath, path)
*res = append(*res, newPath)
}
return
}
for i := start; i <= 9; i++ {
path = append(path, i)
backtrack(res, path, k, n - i, i + 1)
path = path[:len(path) - 1]
}
}
发表回复