回溯算法
回溯题目应用
以力扣https://leetcode.cn/problems/generate-parentheses/submissions/393569541/算法为例:
题目要求:输入一个数字n:数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合
回溯分析过程
先枚举
根据题目要求:可分析得到要生成n对括号,并且括号是有效括号,由于题目要求列出所有组合可能,所以我们要将括号拆分成(
和)
,这样我们一共需要生成2n个这样的括号 先发挥我们的大脑想象😇,列举出这2n个括号的所有排列组合
已n=2为例:
1 | )))) |
可枚举出16种可能,但是这些结果集并不是我们都需要的,因此我们需要针对有效括号的特性做出一些筛减;分析至此,会很轻易发现,这是不是和回溯
的思想很类似呢?回溯的核心思想是:在for循环里面进行递归,枚举出所有可能,在递归调用之前「做选择」,在递归调用之后「撤销选择」;而做选择
就是对穷举的排列组合进行筛减,判断出不合法的选择,然后过滤掉,这种过程通常被叫做剪枝
。撤销选择
即探索过程中发现并不优或达不到目标,就退回一步重新选择
枚举所有可能的代码很好实现:
1 | func GenerateParenthesis(n int) []string { |
递归
递归为什么可实现枚举?
分析过程:
如果输入为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 | var backtrack func (int, string, int, int) |
根据刚才的剪枝分析增加判断条件
1 | // 必须先保证左括号先出现,才能出现右括号 |
由于保证了left出现次数不会超过n/2,并且总出现次数限制为n(n=0时函数会退出),所以右括号数量不能超出n/2的判断代码不用实现
由于函数在递归调用过程中,n由于减1会发生变化,我们需要在全局变量中声明m
并保存n
的初始值
1 | var backtrack func (int, string, int, int) |
完整代码示例
1 | func generateParenthesis(n int) []string { |