力扣回溯算法--总结篇

前言

期末考试加上寒假两个月，一直没有动力，差不多三个月没写题了。最近写题也没有及时写文章总结，实在不知道如何开始，但是也得开始啊。干脆写个总结吧，再开始每天坚持写题写文章。玩了两个月，很多事情没有完成，很多东西也忘得差不多了，得抓紧时间捡起来，坚持输入，坚持输出。

内容

这些天陆陆续续刷的题如下：组合，切割，子集，排列等题型。

回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

回溯法，一般可以解决如下几种问题：

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 子集问题：一个N个数的集合里有多少符合条件的子集
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，解数独等等

回溯法解决的问题可以抽象为树形结构，集合的大小构成了树的宽度，递归的深度构成的树的深度

for循环横向遍历，递归纵向遍历，回溯不断调整结果集。

模板：

var(
    path []int
    res [][]int
)
func findSubsequences(nums []int) [][]int {
 path,res=make([]int,0,len(nums)),make([][]int,0)
 dfs(nums,0)
 return res
}

func dfs(nums []int,start int){
      if len(path)>=2{
        temp:=make([]int,len(path))
        copy(temp,path)
        res=append(res,temp)
      }
      used:=make(map[int]bool,len(nums))
     for i:=start;i<len(nums);i++{
          if used[nums[i]]{
            continue
          }
          if len(path)==0||nums[i]>=path[len(path)-1]{
            //这个条件检查 path 是否为空。如果是，这意味着我们还没有在 path 中添加任何元素，所以我们可以添加 nums[i]，无论它的值是多少。
            //这个条件确保我们添加到 path 中的下一个元素 nums[i] 大于或等于 path 中的最后一个元素。这是为了确保我们正在构建的序列是递增的。
            path=append(path,nums[i])
            used[nums[i]]=true
            dfs(nums,i+1)
            path=path[:len(path)-1]
          }
     }
     
}

最后

加油吧！下一站，贪心算法。