前端关宇的算法学习笔记

backtracking 是 DFS 的一种形式，基本写法类似于 Top Down DFS,但是引入状态回溯？ 这是什么

# backtracking 是 DFS 的一种形式，基本写法类似于 Top Down DFS,但是引入状态回溯？ 这是什么

# 什么是回溯算法 也叫回溯搜索法

  • 本质就是暴力穷举， 穷举所有可能，然后找我们想要的答案， 回溯是下次尝试不要受上次尝试的影响

1 2 345

状态 [] [1] [1,2] [1,2,3] 没有回溯 [1,2,3,4] 有回溯 [1,2,4]

# 不高效为什么还用它？

  • 因为能暴力搜索出来就很不错了

# 可以解决哪些问题？

  • 组合问题 （LeetCode 77 ）
  • 排列问题
  • 切割问题
  • 子集问题
  • 棋盘问题

# 组合和排列的区别？

组合不强调顺序[1,2] 和[2,1] 等价 算是一个

排列强调顺序 [1,2]和[2,1] 是两个 因为顺序不同

# 如何理解回溯法？

  • 构建 决策树
    • 树的深度是递归的深度
    • 树的宽度由集合的大小构成

# 回溯和递归的关系？

  • 回溯通常由递归实现，并且在递归函数的后面 通常就是回溯的代码

# 回溯法的模版？

    1. 回溯函数模版的返回值以及参数
    1. 终止条件
    1. 单层递归逻辑
let backtracking = (参数)=>{
    if(终止条件){
        存放结果
        return //一定要加return
    }
    for(选择 本层集合中的元素 ){
        处理节点
        backtracking(路径， 选择列表)
        回溯 撤销处理结果
    }
}

var backtrack = function(){
    1. base Case
    2. For Each possibility p
        a. Memorize current state
        b. backtrack(next_state)
        c. Restore current state
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# LeetCode 77

  • for 循环嵌套超过三层就很难理解了， 递归实现的话就可以嵌套 n 层， 所以回溯算法里面的解决代码基本都是靠递归，

# 分几种情况

1 元素不重复， 不可重复使用

  • a 子集
  • b 组合 77
  • c 排列

2 元素不重复， 可重复使用

  • a 子集
  • b 组合 39
  • c 排列

3 元素可以重复， 不可重复使用

  • a 子集 90
  • b 组合
  • c 排列

4 元素可以重复可以重复使用， 既然可以重复，就可以重复使用了 ，和 3 一样

所以一共有九种情况

# 回溯可以通过剪枝来优化， 其实就是缩短决策树的宽度（暂时这么理解的）

# 子集问题

k 就是决策树的高度， n 就是决策树的宽度

递归