0%

回溯算法

回溯算法

回溯题目应用

以力扣https://leetcode.cn/problems/generate-parentheses/submissions/393569541/算法为例:

题目要求:输入一个数字n:数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合

回溯分析过程

先枚举

根据题目要求:可分析得到要生成n对括号,并且括号是有效括号,由于题目要求列出所有组合可能,所以我们要将括号拆分成(),这样我们一共需要生成2n个这样的括号 先发挥我们的大脑想象😇,列举出这2n个括号的所有排列组合

已n=2为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
))))
)))(
))()
))((
)())
)()(
)(()
)(((
()))
())(
()()
()((
(())
(()(
((()
((((

可枚举出16种可能,但是这些结果集并不是我们都需要的,因此我们需要针对有效括号的特性做出一些筛减;分析至此,会很轻易发现,这是不是和回溯的思想很类似呢?回溯的核心思想是:在for循环里面进行递归,枚举出所有可能,在递归调用之前「做选择」,在递归调用之后「撤销选择」;而做选择就是对穷举的排列组合进行筛减,判断出不合法的选择,然后过滤掉,这种过程通常被叫做剪枝撤销选择即探索过程中发现并不优或达不到目标,就退回一步重新选择

枚举所有可能的代码很好实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func GenerateParenthesis(n int) []string {
var backtrack func (int, string)
var res = make([]string, 0)
n = n * 2
backtrack = func(n int, back string) {
if n == 0 {
res = append(res, back)
return
}
backtrack(n- 1, back + ")")
backtrack(n- 1, back + "(")
}
backtrack(n, "")
return res
}

递归

递归为什么可实现枚举?

分析过程:

如果输入为2,要生成2n个括号可得出n=4,因为函数是在中调用的,并且递归嵌套调用
所以当:

  • n=1时:backtrack(0, back + ")")backtrack(0, back + "(")都被压入到栈中

  • n=2时:backtrack(1, back + ")")backtrack(1, back + "(")都被压入到栈中

  • n=3时:backtrack(2, back + ")")backtrack(3, back + "(")都被压入到栈中

  • n=4时:backtrack(3, back + ")")backtrack(3, back + "(")都被压入到栈中

不难分析,当:

  • n=0时为终止条件,直接输出

  • n=1时n = n-1 函数调用为backtrack(0, back + ")"),对应了两种结果集:)(都被压入栈中,会输出)(两种可能;函数被压入栈中2次

  • n=2时n = n-1 函数调用为backtrack(1, back + ")"),对应了刚才n=1时两种输出结果集;backtrack(1, back + "(")也对应了n=1的两种输出结果集,想加后一共会输出))((())(四种可能;函数被压入栈中4次

  • n=3时n = n-1 函数调用为backtrack(2, back + ")"),对应了刚才n=2时的两种输出结果集;backtrack(2, back + "(")也对应了n=2的两种输出结果集,想加后一共会输出))) ))( )() )(( ()) ()( (() (((八种可能;函数被压入栈中8次

  • n=4时n = n-1 函数调用为backtrack(3, back + ")"),对应了刚才n=3时的两种输出结果集;backtrack(3, back + "(")也对应了n=3的两种输出结果集,想加后一共会输出…十六种可能;函数被压入栈中16次

  • n=x时n = x-1 函数调用为backtrack(x-1, back + ")")backtrack(x-1, back + "(")对应了2 * (backtrack(x-1))种可能);函数被压入栈中次2 * (backtrack(x-1))

总结:枚举不同可能是一个不断搜索尝试的过程,由于枚举过程需要保存上一次枚举的结果集,而函数参数值在每次函数调用的过程中会保存下来,利用这一特性我们只要在递归终止条件中,将递归后的结果集保存下来就可以穷举出所有可能。

剪枝

剪枝就是在穷举的结果集中过滤到不合法的结果集

根据题意可分析到剪枝条件:

  • 左括号数量不能超出n/2

  • 左括号一定要先于右括号出现

  • 右括号数量不能超出n/2

所以我们要在递归调用中增加函数参数,来保存左括号和右括号出现的次数

1
2
3
4
5
var backtrack func (int, string, int, int)
backtrack = func(n int, back string, left, right int) {
backtrack(n- 1, back + ")", left, right + 1) // 通过right+1实现右括号计数
backtrack(n- 1, back + "(", left + 1, right) // 通过left+1实现左括号计数
}

根据刚才的剪枝分析增加判断条件

1
2
3
4
5
6
7
8
// 必须先保证左括号先出现,才能出现右括号
if left > right {
backtrack(n- 1, back + ")", left, right + 1)
}
// 当左括号出现超过n/2时,剪掉多余的左括号,并且只添加右括号
if left < n / 2 {
backtrack(n- 1, back + "(", left + 1, right)
}

由于保证了left出现次数不会超过n/2,并且总出现次数限制为n(n=0时函数会退出),所以右括号数量不能超出n/2的判断代码不用实现

由于函数在递归调用过程中,n由于减1会发生变化,我们需要在全局变量中声明m并保存n的初始值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var backtrack func (int, string, int, int)
n = n * 2
m := n
backtrack = func(n int, back string, left, right int) {
backtrack(n- 1, back + ")", left, right + 1) // 通过right+1实现右括号计数
backtrack(n- 1, back + "(", left + 1, right) // 通过left+1实现左括号计数
if left > right {
backtrack(n- 1, back + ")", left, right + 1)
}
// 当左括号出现超过n/2时,剪掉多余的左括号,并且只添加右括号
if left < m / 2 {
backtrack(n- 1, back + "(", left + 1, right)
}
}

完整代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func generateParenthesis(n int) []string {
var backtrack func (int, string, int, int)
var res = make([]string, 0)
n = n * 2
m := n
backtrack = func(n int, back string, left, right int) {
if n == 0 {
res = append(res, back)
return
}
//必须先保证左括号先出现,才能出现右括号
if left > right {
backtrack(n- 1, back + ")", left, right + 1)
}
//当左括号出现超过n/2时,剪掉多余的左括号,并且只添加右括号
if left < m / 2 {
backtrack(n- 1, back + "(", left + 1, right)
}
}
backtrack(n, "", 0, 0)
return res
}

img.png