代码随想录 day24 第七章回溯算法part01

本文主要是介绍代码随想录 day24 第七章回溯算法part01，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今日内容：

● 理论基础

● 77. 组合

1. 理论基础

回溯法也叫回溯搜索法
- 是一种搜索方式
递归的副产品，有递归就有回溯
并不高效，本质就是暴力穷举。
组合无序，排列有序
回溯法解决的问题都可以额抽象为树形结构
- N 叉树
回溯法解决的都是在集合中递归查找子集
- 集合的大小就构成了树的宽度，递归的深度，都构成的树的深度

回溯法模板

回溯函数模板返回值以及参数
1. 返回值一般为 void
2. 参数
  1. 一般先写逻辑，根据逻辑中需要的来填写参数
回溯函数终止条件
1. 从树的机构来看：
  1. 搜索到叶子节点，就保存这个答案，结束本层递归

回溯搜索的遍历过程

for Loop 横向遍历
1. 递归纵向遍历

伪代码实现

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果
}

回溯算法模板框架

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

2. 组合

关联 leetcode 77. 组合

思路
- 如果无限的 for loop 嵌套，每 k+1，就要手动多写一次 for loop
  - 不现实
- 把组合抽象为树形结构
  - 输入参数是 n 【1~n】，天然有序
    - 可以逐步收缩集合的选择范围
  - n 是树的宽度，k是树的深度
  - 收集到叶子节点上，就是要找的一个结果
- 回溯法三部曲
  - 递归函数的返回值以及参数
    - rets：最终收集的全局结果集
    - ret：当前次回溯的单词结果集
    - startIdx：当前次开始往后走的起始位置
      - 每次往后递增1步，防止重复取到元素
  - 回溯函数终止条件
    - 走到叶子节点
    - 当前次回溯的单词结果集 == 题目要求的结果集大小【K】
  - 回溯搜索的遍历过程【单层搜索的过程】
    - for循环每次从startIndex开始遍历，然后用ret保存取到的节点i
      - 【Golang注意】：slice底层是数组指针，注意使用copy深拷贝
    - 递归结束后，及时弹出元素，避免重复计算

题解

回溯

func combine(n int, k int) [][]int {rets := make([][]int, 0)ret := make([]int, 0, k)var backtracing func(n int, k int, startIndex int)backtracing = func(n int, k int, startIndex int) {if len(ret) == k {tmp:=make([]int,k)copy(tmp,ret)rets = append(rets, tmp)return}for i := startIndex; i <= n; i++ { // 从start开始，不往回走，避免出现重复组合ret = append(ret, i)backtracing(n, k, i+1)ret = ret[:len(ret)-1]}}backtracing(n, k, 1)return rets
}

剪枝优化

只是对单层搜索逻辑做优化

func combine(n int, k int) [][]int {rets := make([][]int, 0)ret := make([]int, 0, k)var backtracing func(n int, k int, startIndex int)backtracing = func(n int, k int, startIndex int) {if len(ret) == k {tmp := make([]int, k)copy(tmp, ret)rets = append(rets, tmp)return}endIndex := n - (k - len(ret)) + 1 //剪枝, 至多从这里开始回溯for i := startIndex; i <= endIndex; i++ {ret = append(ret, i)backtracing(n, k, i+1)ret = ret[:len(ret)-1]}}backtracing(n, k, 1)return rets
}

这篇关于代码随想录 day24 第七章回溯算法part01的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！