递归分治回溯,bfs专题

递归

模板

  1. 首先规定递归什么时候结束,一定要限制条件,不能无限循环

  2. 递归的执行逻辑,当前层的执行逻辑,即重复性思维,重复性处理,找相似性

  3. 递归调用,层数加1,进入下一层

  4. 最后清除,如果有涉及到外部逻辑的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func recursion(level int, param1, param2 interface{}) {
// recursion terminator递归跳出条件
if level > MAX_LEVEL {
process_result
return
}

// process logic in current level 当前层的执行逻辑
process(level, data...)

// drill down递归调用
recursion(level + 1, p1, ...)

// reverse the current level status if neede 清除收尾
}

注意点

1.递归要找到重复子问题,不要人肉递归

2.一定注意递归终止条件

3.递归属于后进先出(与栈,深度优先遍历类似)

4.明白是层级向下递减,还是递增,带不带return值

递增:边界条件达到最大值,层逻辑在递归调用前处理,看看是不是需要传给下一层

递减:边界条件达到最小值,带返回值,返回后,层逻辑在递归调用后处理,用上一层的返回值处理,看看是不是要用到上一层的结果

分治

1.分治是将递归过程中的问题分步骤解决,每一步骤单独递归,最终得到结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func recursion(level int, param1, param2 interface{}) {
// recursion terminator递归跳出条件
if level > MAX_LEVEL {
process_result
return
}

// 分治处理当前层逻辑
for {
//
process(...)
// drill down递归调用
recursion(...)
}

// reverse the current level status if neede 清除收尾
}

回溯

思想

1.回溯采用试错的思想,分布解决,达到某种特定条件,或者是错误结果,则进行回溯,要有一个不断变化的变量,递归下一层改变,回溯上一层重置

2.递归过程中是一直向深层递归,处理完某种特定条件之后,返回当前层,回到上一层

3.对于当前层的处理进行回溯,回到上一层的状态,进行状态重置

4.在上一层做相应处理,通过分治,走下一种情况去解决,进入到另一种情况下一层,继续处理

5.重复4步骤,知道递归完毕

例如: 组合,全排列等题

1.通过递归往数组里添加数字,直到这个数组,满足结果,添加进最终结果,这个数组就是不断变化的变量

2.然后回溯,将状态回到上一层,再对上一层的分治的第二种情况,继续向下递归,然后回溯,重复步骤

3.区别在于分治时候的逻辑不一样,组合是依次遍历+1,所以不会加入重复的, 全排列是全遍历,要对于已加入的数字进行过滤

复杂度分析

由于回溯相当于遍历,所以时间复杂度会比较高,通过特定条件进行剪枝,跳过一些情况,可以降低复杂度

比如全排列2的排序操作,通过排序预处理,针对已经加入,或者重复的进行跳过,达到剪枝,减少递归

时间复杂度: O(N×N!)
空间复杂度: O(N×N!)

理解

1.为什么要进行回溯,不回溯的话也可以解决问题,则需要在每一层递归的时候,创建新的变量来处理问题,消耗比较大

2.回溯则是用一个变化的变量,进行修改状态,重置状态,不用创建变量

3.回溯问题思考:
1.如何产生分支,如何进行下次递归,递归树是怎样的
2.解在哪里,是在叶子节点,还是路径,还是非叶子节点,如何得到解
3.哪些情况不需要解,如何过滤掉这些解,如何剪枝,如何避免重复

4.要记得优化参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func recursion(level int, param1, param2 interface{}) {
// 得到解,解的条件
terminator(...) {
return
}
// 分治处理
for {
// 剪枝判断,剪枝过滤,减少递归
fix(...)
// 得到解的过程,当前层处理逻辑,变化变量的处理
process(...)

// 进入下一层,变化的变量传入下一层
recursion(...)

// 回溯,回溯变化的变量,回到上一层之后的处理
back()
}
}

例题

括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

递归+回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func generateParenthesis(n int) []string {
res := []string{}
var handle func(int, int, string)
handle = func(left, right int, r string) {
if len(r) == 2*n {
res = append(res, r)
return
}
if left < n {
r += "("
handle(left + 1, right, r)
r = r[:len(r) - 1]
}
if right < left {
r += ")"
handle(left, right + 1, r)
r = r[:len(r) - 1]
}
}

handle(0, 0, "")
return res
}

组合

给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// combine 递归方法
// 1.递归中往数组里添加数字,不断往深递归,达到k的长度要求,则加入结果
// 2.达到结果开始回溯,当前结果满足,则回到上一递归结果,回到上一递归状态
// 3.继续上一个递归的for循环,i++,继续开始下一个数字的组合
func combine(n int, k int) [][]int {
res := [][]int{}
if n < k {
return res
}
var handle func(start int, path []int)
handle = func(start int, path []int) {
// 得到结果的长度,加入结果,加入后进行回溯
if len(path) == k {
// 后续会修改path,需要拷贝,不然数据会修改,path是地址引用
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
return
}
for i := start; i <= n; i++ {
// 1加入
path = append(path, i)
// 从2开始,判断是否到回溯条件,如果符合,加入最终结果
handle(i+1, path)
// 回溯去掉最后一位,继续递归。2完了3,开始下一位循环
path = path[:len(path) - 1]
}

}
handle(1, []int{})
return res
}

全排列

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// permute 递归法,分治回溯
// 1.递归中往数组里添加数字,不断往深递归,达到结果要求,加入最终结果
// 2.满足一种结果后,进行回溯,全排列,相当于每一个空位,每一个数字都有可能
// 3.避免重复,对于已经加入的数字通过map记录,因为是全遍历,再加入时进行过滤
// 4.回溯到上一状态,重置之前加入的数字,重置当前数组
func permute(nums []int) [][]int {
// 结果
res := [][]int{}
// 用于记录访问过的节点
vis := make(map[int]bool, len(nums))
var handle func(curNums []int)
handle = func(curNums []int) {
// 找到结果的条件
if len(curNums) == len(nums) {
// 数组是地址引用,需要拷贝加入最终结果
tmp := make([]int, len(curNums))
copy(tmp, curNums)
res = append(res, tmp)
return
}
// 数组全遍历,要对重复数字进行过滤
for _, v := range nums {
if vis[v] {
continue
}
// 加入结果,并记录
vis[v] = true
curNums = append(curNums, v)
handle(curNums)
// 回溯,重置记录与数组
vis[v] = false
curNums = curNums[:len(curNums) - 1]
}
}
handle([]int{})
return res
}

全排列2

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// permuteUnique 全排列2,包含重复数字
// 1.递归不断往数组中添加数字,往深递归,达到结果长度,加入最终结果
// 2.之后回溯,重置状态
// 3.相比全排列1,包含了重复数字,除了要对已经加入的进行记录过滤,还要对重复数字进行过滤
// 4.为了更好的处理重复,对数组进行排序,重复数字都在一起
// 5.因为包含重复数字,所以记录下标,判断下标是否被记录
// 6.、已经记录的过滤,当前下标值与之前的一样,遇到重复的,且前面一个没有被记录的话,说明是一个新的循环,会产生重复结果,要跳过
func permuteUnique(nums []int) [][]int {
res := [][]int{}
vis := make(map[int]bool, len(nums))
// 数组排序,方便处理重复数据
sort.Ints(nums)

var handle func(curNums []int)
handle = func(curNums []int) {
if len(curNums) == len(nums) {
tmp := make([]int, len(curNums))
copy(tmp, curNums)
res = append(res, tmp)
return
}
for i, v := range nums {
// 已经记录过的跳过
if vis[i] {
continue
}
// 与前面的数字值重复,且前面的数字没有被记录过,说明是新的循环,说明会产生重复结果,跳过
if i > 0 && v == nums[i - 1] && !vis[i - 1] {
continue
}
// 加入数字,记录
vis[i] = true
curNums = append(curNums, v)
handle(curNums)
// 回溯重置
vis[i] = false
curNums = curNums[:len(curNums) - 1]
}
}

handle([]int{})
return res
}

N皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

回溯递归:

1.与之前递归回溯类似,只不过是二维数组,多了一维,可以先初始化一个二维数组,然后在递归过程中不断赋值修改

2.类似组合start +1这种,start就是行, 递归中遍历列,递归深度行+1,达到类似两个指针的效果,就像组合,固定一个,遍历从固定的开始

3.剪枝规则,就是行,左对角线,右对角线都没有重复的

4.递归是另一种遍历,后进先出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func solveNQueens(n int) [][]string {
res := [][]string{}

bd := make([][]string, n)
for i := range bd {
bd[i] = make([]string, n)
for j := range bd[i] {
bd[i][j] = "."
}
}

visCol := make(map[int]bool, n)
visLeftSth := make(map[int]bool, n)
visRightSth := make(map[int]bool, n)

var handle func([][]string, int)
handle = func(bd [][]string, r int) {
if r == n {
tmp := make([]string, n)
for i := 0; i < n; i++ {
tmp[i] = strings.Join(bd[i], "")
}
res = append(res, tmp)
return
}
for c := 0; c < n; c++ {
if visCol[c] || visLeftSth[c - r] || visRightSth[c + r] {
continue
}
bd[r][c] = "Q"
visCol[c] = true
visLeftSth[c - r] = true
visRightSth[c + r] = true
handle(bd, r + 1)
bd[r][c] = "."
visCol[c] = false
visLeftSth[c - r] = false
visRightSth[c + r] = false
}
}
handle(bd, 0)
return res
}

Pow

实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。

for循环迭代会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func myPow(x float64, n int) float64 {
// 处理边界条件
res := 1.0
if n == 0 {
return res
}
// 小于0的时候,负数单独处理
if n < 0 {
x = 1 / x
n = -n
}
// 然后递归,n不断向下递减
var handle func(float64, int) float64
handle = func (x float64, n int) float64 {
// 边界条件
if n == 0 {
return res
}
// 递归调用
res = handle(x, n/2)
// 向上处理
if n % 2 == 0 {
return res * res
}
return res * res * x

}
return handle(x, n)
}

子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

回溯递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func subsets(nums []int) [][]int {
res := [][]int{}

var handle func([]int, int)
handle = func (cur []int, start int) {
if len(cur) <= len(nums) {
tmp := make([]int, len(cur))
copy(tmp, cur)
res = append(res, tmp)
}
for i := start; i < len(nums); i++ {
cur = append(cur, nums[i])
handle(cur, i+1)
cur = cur[:len(cur) - 1]
}
}
handle([]int{}, 0)
return res
}

迭代:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func subsets(nums []int) (ans [][]int) {
n := len(nums)
// << 位操作运算 1<<n
for mask := 0; mask < 1<<n; mask++ {
set := []int{}
for i, v := range nums {
if mask>>i&1 > 0 {
set = append(set, v)
}
}
ans = append(ans, append([]int(nil), set...))
}
return
}

子集2

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

回溯递归:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func subsetsWithDup(nums []int) [][]int {
res := [][]int{}
sort.Ints(nums)
vis := make(map[int]bool, len(nums))

var handle func([]int, int)
handle = func(cur []int, start int) {
if len(cur) <= len(nums) {
tmp := make([]int, len(cur))
copy(tmp, cur)
res = append(res, tmp)
}
for i := start; i < len(nums); i++ {
if i > 0 && nums[i] == nums[i - 1] && !vis[i - 1] {
continue
}

vis[i] = true
cur = append(cur, nums[i])
handle(cur, i + 1)
cur = cur[:len(cur) - 1]
vis[i] = false
}
}
handle([]int{}, 0)
return res
}