回溯算法总结[更新ing]
tbghg

Golang写回溯注意事项

!重点! 最需要注意的三个地方

简记:调用回溯函数、path切片复制装入res、for循环区分 idx 和 i

  1. 闭包写完回溯函数后,不要忘记 调用回溯函数
  2. path装入result时,不可直接添加需要复制
    res = append(res, path),如果path还接着用,那原本装在res的切片也会跟着更改,正确做法:res = append(res, append([]int{}, path...))
  3. for循环内部调用时,注意dfs里传入start(初始值) 还是i(当前值) 还是 其他【比较容易马虎写串】

复制数组时,可以copy,也可以...拆分后重组

1
2
3
4
5
6
// 方法一:copy
tmp := make([]int,len(path)) // 注意:长度必须和path一致
copy(tmp, path)
res = append(res, tmp)
// 方法二:拆分后重组
res = append(res,append([]int{},path...))

注意copy的用法:不会因为srcSlice大而发生扩容,destSlice分配过多少空间就写多少空间

copy( destSlice, srcSlice []T) int

前言

回溯算法规律性太强了,写个总结以后也方便复习。根据代码随想录总结的,插了些自己的看法

回溯介绍

介绍

回溯法也可以叫做回溯搜索法,它是一种搜索的方式。回溯的本质是穷举,但也可以加一些剪枝的操作

有的问题暴力直接写写不出来,此时需要借助回溯实现暴力,回溯可解决的常见问题有:

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

回溯法解决的问题都可以抽象为树形结构

image

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}

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

需要注意力扣中全局变量的用法:力扣全局变量,力扣里面,全局变量只初始化一次,之后只是调用目标函数,所以在函数内部初始化

1
2
3
4
5
6
7
8
9
10
11
var (
path []int
result [][]int
)
// 假设combine为力扣入口函数
func combine(n int, k int) [][]int {
path = make([]int, 0,k) // 全局变量必须函数内部再次初始化
result = make([][]int, 0)
backtrack(n, k, 1)
return result
}

我这里推荐直接写闭包,个人喜欢将回溯函数命名dfs

题目分类

组合问题

介绍

77 组合

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2:

1
2
输入:n = 1, k = 1
输出:[[1]]

提示:

  • 1 <= n <= 20
  • 1 <= k <= n

image

重点:左侧取1的那个分支 会包含 所有 取数组中下表为0的情况,所以之后从2、3、4开始取时不用管那个1了,这个是在回溯内部的for循环中实现的,而 树往下延申 是 通过回溯实现

图中可以发现n相当于树的宽度,k相当于树的深度每次搜索到了叶子节点,我们就找到了一个结果

只需要把达到叶子节点的结果收集起来,就可以求得n个数中k个数的组合集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func combine(n int, k int) [][]int {
path := make([]int, 0, k)
res := make([][]int, 0)
// 先声明再赋值,若直接dfs := func(...){...} 无法在内部递归调用
var dfs func(int)
dfs = func(idx int) {
if len(path) == k {
res = append(res, append([]int{}, path...))
}
for i := idx; i <= n; i++ {
path = append(path, i)
// 进入包含下标为i的分支
dfs(i+1) // 子节点不再重复选自己,所以 i+1
path = path[:len(path)-1]
}
}
dfs(1) // 记着调用
return res
}

注意,回溯的题都要考虑是否可以 剪枝优化

这道题,当 还剩的节点数目 + path中已经选中的 < k ,即 n-i+1 + len(path) < k该节点及其子节点肯定都不满足,没必要接着for循环了,直接return

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func combine(n int, k int) [][]int {
path := make([]int, 0, k)
res := make([][]int, 0)
var dfs func(int)
dfs = func(idx int) {
if len(path) == k {
res = append(res, append([]int{}, path...))
}
for i := idx; i <= n; i++ {
// 剩下?数可选 < 总共还要选?个数
// 也可移项后写入for判断条件中
if n - i + 1 < k - len(path) { // 剪枝
return
}
path = append(path, i)
// 进入包含下标为i的分支
dfs(i+1) // 子节点不再重复选自己,所以 i+1
path = path[:len(path)-1]
}
}
dfs(1) // 记着调用
return res
}

216 组合总和 III

找出所有相加之和为 nk 个数的组合,且满足下列条件:

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

示例 1:

1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

1
2
3
4
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

k 相当于树的深度,9(因为整个集合就是9个数)就是树的宽度

例如 k = 2,n = 4 的话,就是在集合[1,2,3,4,5,6,7,8,9]中求 k(个数) = 2, n(和) = 4的组合。

image

 评论
评论插件加载失败
正在加载评论插件