题目一

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)

分类: 算法

站点统计

  • 文章总数:309 篇
  • 分类总数:19 个
  • 标签总数:190 个
  • 运行天数:975 天
  • 访问总数:72688 人次

浙公网安备33011302000604

辽ICP备20003309号