题目一

leetcode:78

代码与解析一

carl大佬的讲解,是按剩余元素来讲的
回溯三部曲

  • 确定参数及返回值
    需要传入一个startIndex,来记录搜索位置

  • 确定终止条件
    不需要终止条件,因为start``>=len(nums),本层for循环也结束了。也不需要剪枝,因为要遍历整棵树。

  • 确定单层逻辑

tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
for i:=start;i<len(nums);i++{
    path = append(path, nums[i])
    backtracking(i+1)
    path = path[:len(path)-1]
}

整体代码

func subsets(nums []int) [][]int {
    res := [][]int{}
    path := []int{}
    var backtracking func(start int)
    backtracking = func(start int){

        tmp := make([]int, len(path))
        copy(tmp, path)
        res = append(res, tmp)
        for i:=start;i<len(nums);i++{
            path = append(path, nums[i])
            backtracking(i+1)
            path = path[:len(path)-1]
        }
    }
    backtracking(0)
    return res
}

题目二

leetcode:90

代码与解析二

这道题和上一道很像,这道题不同的是:

  • 数组可能包含重复元素

  • 解集不能包含重复的子集

去重的话可以看https://blog.devilwst.top/2021/12/29/组合求和-回溯/这篇文章的第二道

func subsetsWithDup(nums []int) [][]int {
res := [][]int{}
    path := []int{}
    sort.Ints(nums)
    var backtracking func(start int)
    backtracking = func(start int){

        tmp := make([]int, len(path))
        copy(tmp, path)
        res = append(res, tmp)

        for i:=start;i<len(nums);i++{
            if i>start&&nums[i]==nums[i-1]{
                continue
            }
            path = append(path, nums[i])
            backtracking(i+1)
            path = path[:len(path)-1]
        }
    }
    backtracking(0)
    return res
}
分类: 算法

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:864 天
  • 访问总数:474711 人次
ICP备案号: 辽ICP备20003309号