题目一

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

代码与解析二

这道题和上一道很像，这道题不同的是：

• 数组可能包含重复元素

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

去重的话可以看http://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
}