题目一

leetcode:

代码与解析一

这道题和
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
}

题目二

leetcode:40

代码与解析二

这道题和上两道题不同的地方在于：
数组不是有序的，数组可能存在重复元素，而且返回的二维数组里不可以有重复的。
难点在于去重
这里去重要在一个树层上去重。
例如：

去重关键代码：

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)