题目一
代码与解析一
这道题和
https://blog.devilwst.top/2021/12/28/组合总和ⅱ/
https://blog.devilwst.top/2021/12/27/
这两道很像
这道题题目给的是无重复元素的有序数组。!
元素可以重复选取,代码有一点的变化
backtracking(j) //不用j+1了,表示可以重复读取当前的数
其他的代码解析可以看上两道
func combinationSum(candidates []int, target int) [][]int {
res := [][]int{}
path := []int{}
var backtracking func (start int)
backtracking = func(start int){
if sum(path)>target{
return
}
if sum(path)==target{
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
return
}
for j:=start; j<len(candidates);j++{
i := candidates[j]
path = append(path, i)
backtracking(j) //不用j+1了,表示可以重复读取当前的数
path = path[:len(path)-1]
}
}
backtracking(0)
return res
}
func sum(array []int)(res int){
res = 0
for _, v:=range array{
res += v
}
return res
}
题目二
代码与解析二
这道题和上两道题不同的地方在于:
数组不是有序的,数组可能存在重复元素,而且返回的二维数组里不可以有重复的。
难点在于去重
这里去重要在一个树层上去重。
例如:
去重关键代码:
tmp := candidates[i]
// 这里不是i>0哈,一定是start,
if i>start&&tmp==candidates[i-1]{
continue
}
回溯三部曲
- 确定参数及返回值
需要传入startIndex, 和sum。当然和前面两道一样,sum可有可无 -
确定终止条件
按题目要求,如果sumtarget则移到res数组。
然后return -
单层逻辑
先去重,递归加回溯“`go
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
res := [][]int{}
path := []int{}
var backtracking func (start, sum int)
backtracking = func(start, sum int){
if sum>target{
return
}
if sum==target{
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
return
}
for i:=start;i<len(candidates);i++{<pre><code> tmp := candidates[i]
if i>start&&tmp==candidates[i-1]{
continue
}sum += tmp
path = append(path, tmp)
backtracking(i+1, sum)
sum -= tmp
path = path[:len(path)-1]
}
</code></pre><p>}
backtracking(0, 0)
return res
}“`。
[carl大佬的文章里有说一种用used数组去重的方法,没太弄懂](https://programmercarl.com/0040.组合总和II.html#%E5%9B%9E%E6%BA%AF%E4%B8%89%E9%83%A8%E6%9B%B2)